Watch 10 video solutions for Special Array I, a easy level problem involving Array. This walkthrough by Aryan Mittal has 7,342 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |