Is Special Array I easy or hard?

Special Array I is categorized as an Easy problem with a high acceptance rate around 80%. It focuses on basic array traversal and parity logic, making it a common warm-up problem before more complex array or bit manipulation challenges.

Special Array I Python/Java solution

In both Python and Java, iterate through the array and check whether nums[i] % 2 equals nums[i+1] % 2. If they match, return false; otherwise continue. The same logic can also be implemented using a bitwise XOR parity check for constant-time comparisons.

How to solve Special Array I in O(n)?

Traverse the array from index 0 to n-2 and compare the parity of nums[i] and nums[i+1]. If both are even or both are odd, return false immediately. If all adjacent pairs have opposite parity, return true after the loop completes. This requires one pass and constant memory.

What is the best approach for Special Array I?

The best approach is a single linear scan that checks the parity of every adjacent pair. If nums[i] % 2 equals nums[i+1] % 2, the array is not special. This solution runs in O(n) time with O(1) space and is the most straightforward approach expected in interviews.

Is Special Array I asked at Google/Amazon/Meta?

Special Array I represents the type of basic array and parity-check problem commonly used in early interview rounds or coding screens. Variations of parity checks and adjacency constraints appear in interviews at large tech companies including Amazon and Google.

What data structure is used in Special Array I?

The problem primarily uses a simple array traversal. No additional data structures like hash maps or stacks are required because the condition only depends on comparing adjacent elements.

What is the time complexity of Special Array I?

The optimal solution runs in O(n) time because each element is compared with its neighbor exactly once. Space complexity is O(1) since the algorithm only tracks indices and parity checks without allocating extra data structures.

Description Hints 1 Solution Video 16:06

3151. Special Array I

Easy81.6% acceptance6 companies

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 <= 100
1 <= nums[i] <= 100

Asked at 6 companies

National Payments Coorperation India

Google Amazon Microsoft Meta Bloomberg

Topics

Array

Hints open one at a time

Hint 1

Try to check the parity of each element and its previous element.

16:06

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def isArraySpecial(self, nums: List[int]) -> bool:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[1]

Input

[2,1,4]

Input

[4,3,1,6]

Your code is saved on this device.Solution