An array is considered special if every pair of its adjacent elements contains two numbers with different parity.
You are given an array of integers nums. Return true if nums is a special array, otherwise, return false.
Example 1:
Input: nums = [1]
Output: true
Explanation:
There is only one element. So the answer is true.
Example 2:
Input: nums = [2,1,4]
Output: true
Explanation:
There is only two pairs: (2,1) and (1,4), and both of them contain numbers with different parity. So the answer is true.
Example 3:
Input: nums = [4,3,1,6]
Output: false
Explanation:
nums[1] and nums[2] are both odd. So the answer is false.
Constraints:
1 <= nums.length <= 1001 <= nums[i] <= 100Problem Overview: You are given an integer array nums. The array is considered special if every pair of adjacent elements has different parity—one number is even and the other is odd. The task is to verify this condition across the entire array and return true if it holds for every adjacent pair.
Approach 1: Iterative Check (O(n) time, O(1) space)
The most direct solution is to iterate through the array and compare the parity of each adjacent pair. For index i, compute nums[i] % 2 and nums[i+1] % 2. If both results are the same, the two numbers are either both even or both odd, which violates the special array condition. The moment you detect this, return false. If the loop completes without finding such a pair, the array satisfies the requirement.
This approach works because the property only depends on neighboring elements, so you never need additional data structures or preprocessing. It’s a simple linear pass over the array using constant memory. Problems like this often appear in basic array traversal exercises where the key skill is recognizing when a single pass is enough.
Approach 2: Using XOR for Parity Check (O(n) time, O(1) space)
A slightly more elegant approach uses bit manipulation. The least significant bit of a number determines its parity: 0 for even and 1 for odd. If you XOR two numbers, the last bit of the result reveals whether their parity differs. Specifically, (nums[i] ^ nums[i+1]) & 1 equals 1 when one number is even and the other is odd.
During the iteration, compute this expression for each adjacent pair. If the result is 0, the numbers share the same parity and the array is not special. Otherwise continue scanning. This method avoids explicit modulus operations and relies on fast bitwise operations, which are common in bit manipulation patterns.
The logic is still a single linear pass, but it demonstrates a deeper understanding of how parity works at the binary level. Engineers often prefer this approach in performance-sensitive code or when working with low-level operations.
Recommended for interviews: Start with the iterative parity comparison since it’s the most readable and immediately communicates the idea. Mention that the check can also be implemented with XOR on the least significant bit. Interviewers typically expect the O(n) single-pass solution with O(1) extra space, but demonstrating the bitwise variant shows strong familiarity with parity checks and efficient array scanning techniques.
In this approach, we will iterate over the array and check each pair of adjacent elements. We'll verify if they have different parity by comparing them using modulus operation. If all adjacent pairs have different parity, the array is special.
This C function iterates through the array checking each adjacent pair's parity. It returns false if any pair has the same parity, otherwise returns true.
Time Complexity: O(n) where n is the length of the array.
Space Complexity: O(1).
For this approach, we use XOR to check the parity of adjacent elements. Two numbers have different parity iff (x % 2) ^ (y % 2) is true. We loop through the array and if the XOR of adjacent parities is zero, return false.
This C function uses the XOR operation on the parities of adjacent elements to determine if they differ.
Time Complexity: O(n).
Space Complexity: O(1).
We traverse the array from left to right. For each pair of adjacent elements, if their parity is the same, then the array is not a special array, return false; otherwise, the array is a special array, return true.
The time complexity is O(n), where n is the length of the array. The space complexity is $O(1)`.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Iterative Check | Time Complexity: O(n) where n is the length of the array. |
| Using XOR for Parity Check | Time Complexity: O(n). |
| Single Pass | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Parity Check | O(n) | O(1) | Best general approach. Simple linear scan and easiest to explain in interviews. |
| XOR Parity Check | O(n) | O(1) | Useful when applying bit manipulation patterns or optimizing parity checks. |
3152. Special Array II | 3151. Special Array I | Prefix Sums | Arrays • Aryan Mittal • 7,342 views views
Watch 9 more video solutions →Practice Special Array I with our built-in code editor and test cases.
Practice on FleetCode