#3151

Easy

auto_awesomeArray-driven solution strategy

LeetCode Problem Workspace

Special Array I

Determine if an array is special by checking alternating parity for every adjacent pair in linear time.

Problem Statement

A special array is defined as an array where every adjacent pair of elements has different parity, meaning one is even and the other is odd. You are given an array of integers nums and need to determine whether it meets this criteria.

Return true if nums is a special array according to the parity rule, or false if any adjacent elements share the same parity. Examples include nums = [1], which returns true, and nums = [4,3,1,6], which returns false because two consecutive odd numbers appear.

Examples

Example 1

Input: nums = [1]

Output: true

There is only one element. So the answer is true .

Example 2

Input: nums = [2,1,4]

Output: true

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

nums[1] and nums[2] are both odd. So the answer is false .

Constraints

1 <= nums.length <= 100
1 <= nums[i] <= 100

Solution Approach

Single Element Check

If the array has only one element, it is trivially special. Return true immediately without further iteration.

Iterate and Compare Parity

Loop through the array from the second element onward, comparing each element with its previous one. If both are even or both are odd, return false immediately. This direct comparison aligns with the array-driven solution strategy.

Confirm Special Array

If the loop completes without finding any adjacent elements with the same parity, return true. This confirms the array satisfies the alternating parity requirement.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

The time complexity is O(n) because we check each element once, and space complexity is O(1) as no additional structures are used beyond constant variables.

What Interviewers Usually Probe

Checks if candidate immediately handles the single-element array case.
Looks for linear scan comparing current and previous element parity.
Observes whether candidate stops early on failure, showing efficiency.

Common Pitfalls or Variants

Common pitfalls

Forgetting to handle arrays with a single element as a special array.
Incorrectly using modulo operations leading to wrong parity comparisons.
Not stopping early when adjacent elements have the same parity, wasting computation.

Follow-up variants

Check arrays where elements must alternate between multiples of 3 and non-multiples instead of parity.
Determine if an array is special under alternating sign instead of parity.
Handle arrays of larger sizes with streaming input while preserving linear time checks.

FAQ

What defines a special array in the context of Special Array I?

A special array is one where each adjacent pair has different parity, with one element even and the other odd.

Can the solution handle arrays with only one element?

Yes, a single-element array is trivially considered special and should return true.

What is the best approach for checking parity in Special Array I?

Iterate from the second element onward, comparing its parity with the previous element, and return false if any pair matches.

What is the time complexity of this solution?

The solution runs in O(n) time since it checks each element once, with O(1) space.

Are there variants of this problem using different patterns?

Yes, variants include alternating multiples of a number, alternating signs, or handling streaming input arrays.

terminal

Solution

Solution 1: Single Pass

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

1

2

3

class Solution:
    def isArraySpecial(self, nums: List[int]) -> bool:
        return all(a % 2 != b % 2 for a, b in pairwise(nums))

Continue Practicing

#3152 special array ii #3149 find the minimum cost array permutation #3153 sum of digit differences of all pairs