LeetCode Problem 3151

Difficulty: 🟢 Easy
Topics: Array

Solution

Problem Understanding

The problem asks us to determine whether a given integer array is "special". An array is considered special if every pair of adjacent elements has different parity. Parity refers to whether a number is even or odd.

Two numbers have different parity if one is even and the other is odd. For example:

• 2 and 5 have different parity because 2 is even and 5 is odd.
• 7 and 9 do not have different parity because both are odd.
• 4 and 8 do not have different parity because both are even.

The input is an integer array nums. We must return:

• true if every adjacent pair alternates between even and odd
• false if at least one adjacent pair has the same parity

The constraints are small:

• The array length is between 1 and 100
• Each number is between 1 and 100

These constraints tell us that performance is not a major concern. Even an inefficient solution would run quickly for such a small input size. However, the goal is still to write a clean and optimal solution.

Several edge cases are important:

• A single-element array is always special because there are no adjacent pairs to violate the rule.
• Arrays where all numbers are even or all numbers are odd should immediately return false once two adjacent equal parities are found.
• Alternating parity arrays such as [1,2,3,4] should return true.
• The first invalid adjacent pair should allow an early exit instead of continuing unnecessary checks.

Approaches

Brute Force Approach

The brute-force solution checks every adjacent pair in the array and determines whether both numbers have the same parity.

For each index i, we compare:

• nums[i] % 2
• nums[i + 1] % 2

If the remainders are equal, both numbers are either even or odd, meaning the array is not special.

This approach is already efficient enough for the given constraints because the array size is very small. Since every element must be checked at most once, the runtime is linear.

Key Insight for the Optimal Approach

The key observation is that the property of a special array depends only on adjacent pairs.

We do not need any extra data structures, preprocessing, or nested loops. The moment we find two consecutive numbers with the same parity, we can immediately return false.

This allows a very clean single-pass solution:

• Traverse the array once
• Compare each pair of neighbors
• Stop early if a violation is found
• Return true if the loop finishes successfully

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Checks every adjacent pair directly
Optimal	O(n)	O(1)	Single-pass traversal with early termination

In this problem, the brute-force and optimal approaches are effectively the same because checking adjacent pairs is already the minimal work required.

Algorithm Walkthrough

1. Start iterating from index 0 to len(nums) - 2.
2. For each index i, examine the current number nums[i] and the next number nums[i + 1].
3. Compute the parity of both numbers using modulo:

• Even numbers produce 0 with % 2
• Odd numbers produce 1 with % 2

4. Compare the two parity values.

• If they are equal, both numbers have the same parity.
• In that case, the array is not special, so return false immediately.

5. If the loop completes without finding any invalid adjacent pair, return true.

Why it works

The definition of a special array depends entirely on adjacent pairs. The algorithm checks every adjacent pair exactly once. If any pair violates the alternating parity condition, the algorithm immediately returns false. If no violations exist after checking all pairs, every adjacent pair must have different parity, which means the array is special. The problem asks us to determine whether an array of integers is special, meaning that every pair of adjacent elements in the array must have different parity. Parity refers to whether a number is even or odd. For any two consecutive elements nums[i] and nums[i+1], one must be even and the other odd. If any adjacent pair shares the same parity (both even or both odd), the array is not special.

The input is a list of integers nums where the length is guaranteed to be between 1 and 100, and each integer is between 1 and 100. The expected output is a boolean: true if the array is special and false otherwise.

Important edge cases include arrays of length 1, which are trivially special because there are no adjacent pairs to compare, and arrays where all numbers are the same parity, which should immediately return false if length is greater than 1. The problem guarantees that all inputs are positive integers, so we do not need to handle negative numbers or zeros.

Approaches

The brute-force approach iterates through the array and compares every adjacent pair. For each pair, we check whether both elements are even or both are odd. If such a pair is found, we immediately return false. If we reach the end of the array without finding any conflicting pair, we return true. This approach works correctly because it explicitly verifies the definition of a special array.

The key insight for an optimal approach is that we do not need any complex data structures or sorting. We only need to check parity alternation between consecutive elements. Since each comparison is constant time and we only traverse the array once, this is already optimal. The constraints are small (length up to 100), so the straightforward check is sufficient.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n)	O(1)	Iterates through the array comparing adjacent elements
Optimal	O(n)	O(1)	Single pass, directly checks parity alternation

Algorithm Walkthrough

1. Check if the array has only one element. If so, return true because a single-element array is trivially special.
2. Iterate over the array from the first element to the second-to-last element. For each index i, compare nums[i] and nums[i+1].
3. For each pair, calculate nums[i] % 2 and nums[i+1] % 2 to determine parity.
4. If the parities are the same, return false immediately because the array is no longer special.
5. If all adjacent pairs have different parity, return true after finishing the iteration.

Why it works: The algorithm maintains the invariant that every checked pair so far alternates in parity. By checking all adjacent pairs, we ensure that the definition of a special array is satisfied. The algorithm is complete and correct because it considers all necessary pairs and terminates as soon as a violation is detected.

Python Solution

from typing import List

class Solution:
    def isArraySpecial(self, nums: List[int]) -> bool:
        for i in range(len(nums) - 1):
            if nums[i] % 2 == nums[i + 1] % 2:
        if len(nums) == 1:
            return True
        
        for i in range(len(nums) - 1):
            if nums[i] % 2 == nums[i+1] % 2:
                return False
        
        return True

The implementation follows the exact algorithm described earlier.

The loop runs from 0 to len(nums) - 2 because each iteration compares an element with its next neighbor.

Inside the loop, % 2 determines parity:

• 0 means even
• 1 means odd

If two adjacent numbers produce the same remainder, they have the same parity, so the function immediately returns False.

If the loop finishes without finding a violation, the function returns True, meaning every adjacent pair alternates parity correctly. This implementation first handles the edge case of a single-element array. Then, it iterates over the array comparing adjacent elements for parity. If any pair has the same parity, it immediately returns false. Otherwise, it returns true at the end. This directly mirrors the algorithm walkthrough.

Go Solution

func isArraySpecial(nums []int) bool {
    if len(nums) == 1 {
        return true
    }
    
    for i := 0; i < len(nums)-1; i++ {
        if nums[i]%2 == nums[i+1]%2 {
            return false
        }
    }

    
    return true
}

The Go implementation is nearly identical to the Python version.

The loop iterates through adjacent pairs using standard indexing. The modulo operator % is used to determine parity exactly as in Python.

No special handling is needed for empty arrays because the problem guarantees at least one element. Go slices are used naturally for array access, and integer overflow is not a concern because the values are very small.

Worked Examples

Example 1

Input:

nums = [1]

Since there is only one element, there are no adjacent pairs to check.

The loop does not execute because len(nums) - 1 equals 0.

Result:

true

Example 2

Input:

nums = [2,1,4]

Iteration	Current Pair	Parities	Same Parity?	Result
1	(2, 1)	(0, 1)	No	Continue
2	(1, 4)	(1, 0)	No	Continue

No invalid pair is found.

Result:

true

Example 3

Input:

nums = [4,3,1,6]

Iteration	Current Pair	Parities	Same Parity?	Result
1	(4, 3)	(0, 1)	No	Continue
2	(3, 1)	(1, 1)	Yes	Return false

The algorithm stops immediately once it finds two adjacent odd numbers.

Result:

false

The Go implementation is almost identical to the Python version. It handles arrays of length 1, iterates through the slice, and compares the parity of adjacent elements. Since Go slices are zero-indexed and support the len() function, the implementation is straightforward.

Worked Examples

Example 1: nums = [1]

Length is 1, so return true.

Example 2: nums = [2, 1, 4]

i	nums[i]	nums[i+1]	nums[i]%2	nums[i+1]%2	Comparison	Result
0	2	1	0	1	different	continue
1	1	4	1	0	different	continue

All pairs pass, return true.

Example 3: nums = [4, 3, 1, 6]

i	nums[i]	nums[i+1]	nums[i]%2	nums[i+1]%2	Comparison	Result
0	4	3	0	1	different	continue
1	3	1	1	1	same	return false

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each adjacent pair is checked once
Space	O(1)	Only a few variables are used

The algorithm performs a single pass through the array. Since each element participates in at most one comparison with its neighbor, the runtime grows linearly with the array size.

The space usage is constant because no additional data structures are created. | Time | O(n) | Each element is visited once for parity comparison | | Space | O(1) | No extra data structures, only a few variables for iteration |

The reasoning is that the algorithm performs a single pass through the array, and we only use constant extra space, making it optimal for the input size constraints.

Test Cases

sol = Solution()

assert sol.isArraySpecial([1]) == True  # Single element array
assert sol.isArraySpecial([2, 1, 4]) == True  # Alternating even and odd
assert sol.isArraySpecial([4, 3, 1, 6]) == False  # Two adjacent odd numbers
assert sol.isArraySpecial([2, 4, 6]) == False  # All even numbers
assert sol.isArraySpecial([1, 3, 5]) == False  # All odd numbers
assert sol.isArraySpecial([1, 2, 3, 4, 5]) == True  # Perfect alternation
assert sol.isArraySpecial([1, 2, 4, 5]) == False  # Adjacent even numbers
assert sol.isArraySpecial([2, 1]) == True  # Small valid array
assert sol.isArraySpecial([2, 2]) == False  # Small invalid array
assert sol.isArraySpecial([99, 100, 101, 102]) == True  # Larger values alternating parity

Test Summary

Test	Why
[1]	Validates single-element edge case
[2,1,4]	Standard valid alternating parity case
[4,3,1,6]	Detects adjacent odd numbers
[2,4,6]	Detects adjacent even numbers
[1,3,5]	Detects all odd sequence
[1,2,3,4,5]	Verifies long alternating pattern
[1,2,4,5]	Tests failure in the middle
[2,1]	Smallest valid multi-element array
[2,2]	Smallest invalid multi-element array
[99,100,101,102]	Confirms correctness with larger values

Edge Cases

A single-element array is an important edge case because there are no adjacent pairs to compare. A naive implementation might accidentally assume at least two elements exist and cause an index error. This implementation handles it naturally because the loop executes zero times and returns True.

Arrays containing all even or all odd numbers are another important case. These arrays fail immediately because the very first adjacent pair shares the same parity. The implementation correctly detects this during the first comparison and exits early.

Cases where the invalid pair appears in the middle of the array can expose bugs in implementations that only partially validate the array. For example, [1,2,4,5] starts correctly but contains adjacent even numbers in the middle. The algorithm checks every adjacent pair sequentially, ensuring such violations are always detected.

Another subtle case is arrays that alternate correctly until the final pair. For example, [1,2,3,6] fails only at the end because 3 and 6 have different parity, actually valid, while [1,2,4,6] fails at the final pair because 4 and 6 are both even. The implementation checks every pair up to the last valid index, ensuring end-of-array violations are handled properly.

test cases

assert Solution().isArraySpecial([1]) == True # single element assert Solution().isArraySpecial([2,1,4]) == True # alternating parity assert Solution().isArraySpecial([4,3,1,6]) == False # two consecutive odd numbers assert Solution().isArraySpecial([2,4,6,8]) == False # all even assert Solution().isArraySpecial([1,3,5,7]) == False # all odd assert Solution().isArraySpecial([1,2,3,4,5,6]) == True # perfect alternation assert Solution().isArraySpecial([2,1,2,1,2,1]) == True # another alternating pattern assert Solution().isArraySpecial([2,2,1,1]) == False # consecutive same parity at start and middle assert Solution().isArraySpecial([1,2,4,3,6]) == False # fails in middle

| Test | Why |
| --- | --- |
| [1] | Single element, trivially special |
| [2,1,4] | Alternating parity, should return true |
| [4,3,1,6] | Two consecutive odd numbers, should return false |
| [2,4,6,8] | All even, should return false |
| [1,3,5,7] | All odd, should return false |
| [1,2,3,4,5,6] | Perfect alternation, should return true |
| [2,1,2,1,2,1] | Alternating pattern, should return true |
| [2,2,1,1] | Same parity at start and middle, should return false |
| [1,2,4,3,6] | Fails in the middle, should return false |

## Edge Cases

One important edge case is a single-element array. It has no adjacent elements, so it is trivially special. Any implementation must handle this separately, as comparing elements would be invalid. The provided solution returns `true` immediately.

Another edge case is when all elements have the same parity. This should return `false` as soon as the first pair is checked. This helps catch naive implementations that only check some pairs or assume an array can start with any parity.

A third edge case involves arrays where alternation fails somewhere in the middle. It tests whether the algorithm correctly stops early and does not falsely return `true`. By iterating through all pairs and returning `false` immediately upon a parity match, the implementation correctly handles this case.