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:
[4,3,1]. 3 and 1 are both odd. So the answer to this query is false.[1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1051 <= queries.length <= 105queries[i].length == 20 <= queries[i][0] <= queries[i][1] <= nums.length - 1This approach involves iterating over each subarray defined by the queries and checking every adjacent pair for differing parity. The naive nature of this method makes it straightforward but potentially inefficient for larger inputs.
In this C solution, we iterate over each query range, checking adjacent pairs in the subarray for parity differences. If any pair has the same parity, the subarray is not special.
C++
Java
Python
C#
JavaScript
Time Complexity: O(queriesSize × numsSize).
Space Complexity: O(1) if output array is not considered.
This approach leverages the use of a prefix array to determine segment misfits based on parity changes. By preprocessing the array into a prefix difference array, each query can be answered in constant time by checking if any parity changes exist within the given range.
The C code creates a difference array storing whether adjacents differ in parity, then checks titles per query efficiently using this preprocessed information.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + q) where n = numsSize and q = queriesSize.
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(queriesSize × numsSize). |
| Prefix Parity Difference Array | Time Complexity: O(n + q) where n = numsSize and q = queriesSize. |
India - This one is for you! Special Array, Leetcode 3151 • Greg Hogg • 54,904 views views
Watch 9 more video solutions →Practice Special Array II with our built-in code editor and test cases.
Practice on FleetCode