Special Array II
MedPrompt
An array is considered special if every pair of its adjacent elements contains two numbers with different parity.
You are given an array of integer nums and a 2D integer matrix queries, where for queries[i] = [fromi, toi] your task is to check that subarray nums[fromi..toi] is special or not.
Return an array of booleans answer such that answer[i] is true if nums[fromi..toi] is special.
Example 1:
Input: nums = [3,4,1,2,6], queries = [[0,4]]
Output: [false]
Explanation:
The subarray is [3,4,1,2,6]. 2 and 6 are both even.
Example 2:
Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]
Output: [false,true]
Explanation:
- The subarray is
[4,3,1]. 3 and 1 are both odd. So the answer to this query isfalse. - The subarray is
[1,6]. There is only one pair:(1,6)and it contains numbers with different parity. So the answer to this query istrue.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1
Approaches
2 approaches with complexity analysis and trade-offs.
This approach directly translates the problem statement into code. For each query, it iterates through the specified subarray and checks if every adjacent pair of elements has different parity. It is the most straightforward but least efficient method.
Algorithm
-
- Initialize a boolean array
answerwith the same size asqueries.
- Initialize a boolean array
-
- Loop through each query
[from, to]from thequeriesmatrix.
- Loop through each query
-
- For each query, handle the base case where
from == to; the subarray is always special.
- For each query, handle the base case where
-
- If
from != to, loop from indexj = fromtoto - 1.
- If
-
- Inside the inner loop, check if
nums[j]andnums[j+1]have the same parity using the modulo operator:(nums[j] % 2) == (nums[j+1] % 2).
- Inside the inner loop, check if
-
- If they have the same parity, the subarray is not special. Mark the result for the current query as
falseand break the inner loop to proceed to the next query.
- If they have the same parity, the subarray is not special. Mark the result for the current query as
-
- If the inner loop completes without finding any pair with the same parity, the subarray is special. Mark the result as
true.
- If the inner loop completes without finding any pair with the same parity, the subarray is special. Mark the result as
-
- After processing all queries, return the
answerarray.
- After processing all queries, return the
Walkthrough
We can solve this problem by iterating through each query one by one. For a given query [from, to], we check every adjacent pair of numbers in the subarray nums[from...to].
A subarray is special if for all i from from to to - 1, the parity of nums[i] is different from the parity of nums[i+1]. We can check the parity of a number using the modulo operator (number % 2). If nums[i] % 2 is equal to nums[i+1] % 2, their parities are the same, and the subarray is not special. We can then immediately stop checking for this query and move to the next one.
If we iterate through all adjacent pairs in the subarray and don't find any with the same parity, the subarray is special. A subarray with a single element (from == to) is always considered special.
class Solution { public boolean[] isSpecialArray(int[] nums, int[][] queries) { boolean[] answer = new boolean[queries.length]; for (int i = 0; i < queries.length; i++) { int from = queries[i][0]; int to = queries[i][1]; if (from == to) { answer[i] = true; continue; } // Assume the subarray is special initially boolean isSpecial = true; // Check all adjacent pairs in the subarray for (int j = from; j < to; j++) { if ((nums[j] % 2) == (nums[j + 1] % 2)) { isSpecial = false; break; // Found a non-special pair, no need to check further } } answer[i] = isSpecial; } return answer; }}Complexity
Time
O(Q * N), where `Q` is the number of queries and `N` is the length of `nums`. In the worst case, each query could span the entire array, leading to `Q * N` operations.
Space
O(Q) to store the output array. If the output array is not considered part of the space complexity, it is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space besides the output array, making it memory efficient.
Cons
Highly inefficient for large inputs due to its quadratic time complexity in the worst case.
Will result in a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
Repeatedly re-computes results for overlapping subarrays, which is redundant work.
This is an optimized approach that avoids re-computation by preprocessing the input array. We can identify all adjacent pairs with the same parity (let's call them "bad pairs") and use a prefix sum array to count them. A query for a subarray [from, to] can then be answered in constant time by checking if there are any "bad pairs" within that range.
Algorithm
-
- Create a prefix sum array
prefixBadCountof sizen(length ofnums).
- Create a prefix sum array
-
- Initialize
prefixBadCount[0] = 0.
- Initialize
-
- Iterate from
i = 1ton-1. For eachi, setprefixBadCount[i] = prefixBadCount[i-1]. Ifnums[i]andnums[i-1]have the same parity, incrementprefixBadCount[i].
- Iterate from
-
- Initialize an answer array
answerof sizeq(number of queries).
- Initialize an answer array
-
- Iterate through each query
[from, to].
- Iterate through each query
-
- For each query, calculate the number of "bad pairs" in the subarray
nums[from...to]asprefixBadCount[to] - prefixBadCount[from].
- For each query, calculate the number of "bad pairs" in the subarray
-
- If the result is 0, the subarray is special, so set
answer[i] = true. Otherwise, setanswer[i] = false.
- If the result is 0, the subarray is special, so set
-
- Return the
answerarray.
- Return the
Walkthrough
A subarray nums[from...to] is special if and only if there are no indices i (where from <= i < to) such that nums[i] and nums[i+1] have the same parity.
We can precompute an array, let's call it prefixBadCount, of size n (length of nums). prefixBadCount[i] will store the total number of "bad pairs" in the prefix of the array nums[0...i]. A "bad pair" is an adjacent pair of elements with the same parity.
The prefixBadCount array is built as follows:
prefixBadCount[0] = 0.- For
ifrom 1 ton-1,prefixBadCount[i] = prefixBadCount[i-1]. If the pair(nums[i-1], nums[i])is a bad pair (i.e.,nums[i-1] % 2 == nums[i] % 2), we incrementprefixBadCount[i]by 1.
After building this prefix sum array, we can answer any query [from, to] in O(1) time. The number of bad pairs in the subarray nums[from...to] corresponds to the bad pairs at indices (from, from+1), (from+1, from+2), ..., (to-1, to). The total count of these bad pairs can be calculated as prefixBadCount[to] - prefixBadCount[from]. If this difference is 0, it means there are no bad pairs in the subarray, so it's special. Otherwise, it's not.
class Solution { public boolean[] isSpecialArray(int[] nums, int[][] queries) { int n = nums.length; int[] prefixBadCount = new int[n]; // prefixBadCount[i] stores the number of adjacent pairs with the same parity // in the prefix nums[0...i]. The check is for the pair (nums[i-1], nums[i]). for (int i = 1; i < n; i++) { prefixBadCount[i] = prefixBadCount[i - 1]; if ((nums[i] % 2) == (nums[i - 1] % 2)) { prefixBadCount[i]++; } } int q = queries.length; boolean[] answer = new boolean[q]; for (int i = 0; i < q; i++) { int from = queries[i][0]; int to = queries[i][1]; if (from == to) { answer[i] = true; continue; } // The number of bad pairs in the subarray nums[from...to] is the // number of bad pairs up to index 'to' minus the number of bad pairs // up to index 'from'. int badPairsInSubarray = prefixBadCount[to] - prefixBadCount[from]; answer[i] = (badPairsInSubarray == 0); } return answer; }}Complexity
Time
O(N + Q), where `N` is the length of `nums` and `Q` is the number of queries. `O(N)` for preprocessing and `O(Q)` for answering all queries.
Space
O(N + Q). `O(N)` for the prefix sum array and `O(Q)` for the output array. If the output array is not considered, the space complexity is `O(N)`.
Trade-offs
Pros
Highly efficient, with a linear time complexity overall.
Answers each query in constant time after an initial linear-time preprocessing step.
Perfectly suited for problems with a large number of range queries on a static array.
Cons
Requires additional space proportional to the size of the input array
numsfor the prefix sum array.
Solutions
Solution
class Solution {public boolean[] isArraySpecial(int[] nums, int[][] queries) { int n = nums.length; int[] d = new int[n]; for (int i = 1; i < n; ++i) { if (nums[i] % 2 != nums[i - 1] % 2) { d[i] = d[i - 1]; } else { d[i] = i; } } int m = queries.length; boolean[] ans = new boolean[m]; for (int i = 0; i < m; ++i) { ans[i] = d[queries[i][1]] <= queries[i][0]; } return ans; }}class Solution {public: vector<bool> isArraySpecial(vector<int> &nums, vector<vector<int>> &queries) { int n = nums.size(); vector<int> d(n); iota(d.begin(), d.end(), 0); for (int i = 1; i < n; ++i) { if (nums[i] % 2 != nums[i - 1] % 2) { d[i] = d[i - 1]; } } vector<bool> ans; for (auto &q : queries) { ans.push_back(d[q[1]] <= q[0]); } return ans; }};class Solution: def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]: n = len(nums) d = list(range(n)) for i in range(1, n): if nums[i] % 2 != nums[i - 1] % 2: d[i] = d[i - 1] return [d[t] <= f for f, t in queries]Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.