Problem Description

You need to determine if an array has a special property where every pair of adjacent elements has different parity (one is even and one is odd).

Given an array of integers nums, you should check if it's "special" by verifying that for every consecutive pair of elements in the array, one element must be even and the other must be odd. The order doesn't matter - it could be even-odd or odd-even, as long as they're different.

For example:

• [2, 1, 4] is special because 2 (even) and 1 (odd) have different parity, and 1 (odd) and 4 (even) have different parity
• [2, 4, 1] is not special because 2 (even) and 4 (even) have the same parity

The solution uses Python's pairwise function to create consecutive pairs from the array, then checks each pair using a % 2 != b % 2 to ensure the remainders when divided by 2 are different (indicating different parity). The all() function returns True only if every pair satisfies this condition.

Return true if the array is special, false otherwise.

Intuition

The key insight is recognizing that checking if two numbers have different parity is equivalent to checking if their remainders when divided by 2 are different. When we divide any integer by 2, we get a remainder of either 0 (for even numbers) or 1 (for odd numbers).

To check if an array is special, we need to verify that no two consecutive elements have the same parity. This naturally leads us to think about examining pairs of adjacent elements throughout the array.

The thought process goes like this:

1. We need to look at every consecutive pair in the array
2. For each pair (a, b), we need to check if one is even and the other is odd
3. Instead of explicitly checking if one is even and one is odd, we can simply check if a % 2 != b % 2
4. If any pair fails this check, the array is not special
5. If all pairs pass this check, the array is special

This leads to a clean one-liner solution using Python's pairwise function to generate consecutive pairs and all() to ensure every pair satisfies our parity difference condition. The expression a % 2 != b % 2 elegantly captures the requirement that adjacent elements must have different parity values.

Solution Approach

The solution uses a single pass traversal to check if the array is special. Here's how the implementation works:

1. Iterate through adjacent pairs: We use Python's pairwise function to generate all consecutive pairs from the array. For an array like [1, 2, 3, 4], pairwise generates (1, 2), (2, 3), (3, 4).

2. Check parity difference: For each pair (a, b), we calculate a % 2 and b % 2. These operations give us:

   • 0 if the number is even
   • 1 if the number is odd

3. Compare remainders: We check if a % 2 != b % 2. This condition is True when:

   • a is even (remainder 0) and b is odd (remainder 1), or
   • a is odd (remainder 1) and b is even (remainder 0)

4. Verify all pairs: The all() function returns True only if the parity check passes for every single pair. If even one pair has the same parity (both even or both odd), all() returns False.

The entire check is done in a single line: all(a % 2 != b % 2 for a, b in pairwise(nums)). This approach has a time complexity of O(n) where n is the length of the array, as we visit each element exactly once. The space complexity is O(1) as we only use a constant amount of extra space for the iteration.

Example Walkthrough

Let's walk through the solution with the array [4, 3, 1, 6].

Step 1: Generate consecutive pairs Using pairwise([4, 3, 1, 6]), we get:

• Pair 1: (4, 3)
• Pair 2: (3, 1)
• Pair 3: (1, 6)

Step 2: Check each pair's parity

For Pair 1: (4, 3)

• 4 % 2 = 0 (even)
• 3 % 2 = 1 (odd)
• 0 != 1 → True ✓

For Pair 2: (3, 1)

• 3 % 2 = 1 (odd)
• 1 % 2 = 1 (odd)
• 1 != 1 → False ✗

Since we found a pair where both elements have the same parity (both odd), the array is not special.

The all() function would return False because not all pairs satisfy the condition.

Let's contrast this with a special array [2, 5, 4]:

Step 1: Generate consecutive pairs

• Pair 1: (2, 5)
• Pair 2: (5, 4)

Step 2: Check each pair's parity

For Pair 1: (2, 5)

• 2 % 2 = 0 (even)
• 5 % 2 = 1 (odd)
• 0 != 1 → True ✓

For Pair 2: (5, 4)

• 5 % 2 = 1 (odd)
• 4 % 2 = 0 (even)
• 1 != 0 → True ✓

All pairs have different parity, so the array is special and the function returns True.

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array. The pairwise function generates consecutive pairs from the array, creating n-1 pairs. The all() function iterates through these pairs once, checking if each pair has different parity (one odd, one even) using the modulo operation a % 2 != b % 2. Since each comparison is O(1) and we perform n-1 comparisons, the overall time complexity is O(n).

The space complexity is O(1). The pairwise function returns an iterator that generates pairs on-the-fly without storing all pairs in memory. The all() function processes this iterator without creating additional data structures. Only a constant amount of extra space is used for the iterator state and temporary variables a and b, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Handling Single-Element Arrays

The most common pitfall is not considering edge cases where the array has only one element. A single-element array has no adjacent pairs to check, so it should be considered "special" by default.

The Problem:

# This might fail or behave unexpectedly for single elements
return all(a % 2 != b % 2 for a, b in pairwise(nums))

When nums = [5], pairwise([5]) generates an empty iterator, and all() on an empty sequence returns True. While this happens to give the correct result, it's not immediately obvious why.

The Solution: Make the edge case handling explicit:

def isArraySpecial(self, nums: List[int]) -> bool:
    # Single element or empty arrays are special by definition
    if len(nums) <= 1:
        return True
  
    return all(a % 2 != b % 2 for a, b in pairwise(nums))

2. Using Index-Based Iteration Without Bounds Checking

If not using pairwise, developers often iterate with indices and forget to adjust the loop bounds:

The Problem:

# This will cause IndexError
for i in range(len(nums)):
    if nums[i] % 2 == nums[i + 1] % 2:  # IndexError when i = len(nums) - 1
        return False

The Solution:

# Correct index-based approach
for i in range(len(nums) - 1):  # Stop one element before the end
    if nums[i] % 2 == nums[i + 1] % 2:
        return False
return True

3. Incorrectly Checking for Alternating Pattern Starting Position

Some might mistakenly think the array must follow a strict alternating pattern starting with a specific parity:

The Problem:

# Wrong: This checks if array strictly alternates starting with even/odd
def isArraySpecial(self, nums: List[int]) -> bool:
    for i in range(len(nums)):
        if nums[i] % 2 != i % 2:  # Incorrect logic
            return False
    return True

This would incorrectly reject [1, 2, 3] because it expects index 0 to be even.

The Solution: Focus only on adjacent pairs having different parity, not on any specific pattern:

return all(a % 2 != b % 2 for a, b in pairwise(nums))