Special Array I - Solution & Explanation

Problem 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.