Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Special Array I solution and explanation

EasyArray5 min read81.6% acceptanceUpdated 9 Apr 2026
Asked atNational Payments Coorperation IndiaGoogleAmazonMicrosoftMetaBloomberg
Practise Special Array I
16:06
3152. Special Array II | 3151. Special Array I | Prefix Sums | ArraysAryan Mittal · 16:06 · 7K viewsWatch on YouTube
9 more videos on this problem
  1. 3152. Special Array II | 3151. Special Array I | Prefix Sums | ArraysAryan Mittal · 16:06 · 7K views
  2. Special Array I - Leetcode 3151 - PythonNeetCodeIO · 3:33 · 5K views
  3. Special Array I | 2 Approaches | Leetcode 3151 | codestorywithMIKcodestorywithMIK · 7:56 · 4K views
  4. Special Array I | Leetcode 3151Techdose · 4:01 · 1K views
  5. Leetcode | 3151. Special Array I | Easy | Java SolutionDeveloper Docs · 4:32 · 519 views
  6. 3151. Special Array I | Leetcode Daily ChallengeEthos Typos · 4:58 · 347 views
  7. 3151. Special Array I (Leetcode Easy)Programming Live with Larry · 2:14 · 291 views
  8. 3151. Special Array I | LeetCode Weekly Contest 398 | TUROTIAL - 46Coding Kart · 8:40 · 176 views
  9. Daily Leetcode #1768: Feb 01, 2025 - 3151. Special Array IProgramming Live with Larry · 4:51 · 167 views
  10. LeetCode 3151 Special Array 1 Solve this EASY QUESTION in LEETCODE simple FOR LOOP conditionR Sai Siddhu · 3:15 · 150 views

The problem

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

Approach overview

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.

Approach 1: Iterative Check

In this approach, we will iterate over the array and check each pair of adjacent elements. We'll verify if they have different parity by comparing them using modulus operation. If all adjacent pairs have different parity, the array is special.

def is_special_array(nums):
    for i in range(len(nums) - 1):
        if (nums[i] % 2) == (nums[i + 1] % 2):
            return False
    return True
class Solution {
    public boolean isSpecialArray(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if ((nums[i] % 2) == (nums[i + 1] % 2)) {
                return false;
            }
        }
        return true;
    }
}
#include <vector>
using namespace std;

class Solution {
public:
    bool isSpecialArray(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; ++i) {
            if ((nums[i] % 2) == (nums[i + 1] % 2)) {
                return false;
            }
        }
        return true;
    }
};
function isSpecialArray(nums) {
    for (let i = 0; i < nums.length - 1; i++) {
        if ((nums[i] % 2) === (nums[i + 1] % 2)) {
            return false;
        }
    }
    return true;
}
#include <stdbool.h>

bool isSpecialArray(int* nums, int numsSize) {
    for (int i = 0; i < numsSize - 1; i++) {
        if ((nums[i] % 2) == (nums[i + 1] % 2)) {
            return false;
        }
    }
    return true;
}
public class Solution {
    public bool IsSpecialArray(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i++) {
            if ((nums[i] % 2) == (nums[i + 1] % 2)) {
                return false;
            }
        }
        return true;
    }
}

The Python function iterates through the array to check each adjacent pair of elements for parity differences. Returns false if any two are the same.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 2: Using XOR for Parity Check

For this approach, we use XOR to check the parity of adjacent elements. Two numbers have different parity iff (x % 2) ^ (y % 2) is true. We loop through the array and if the XOR of adjacent parities is zero, return false.

def is_special_array(nums):
    for i in range(len(nums) - 1):
        if not ((nums[i] % 2) ^ (nums[i + 1] % 2)):
            return False
    return True
class Solution {
    public boolean isSpecialArray(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (!((nums[i] % 2) ^ (nums[i + 1] % 2))) {
                return false;
            }
        }
        return true;
    }
}
#include <vector>
using namespace std;

class Solution {
public:
    bool isSpecialArray(vector<int>& nums) {
        for (int i = 0; i < nums.size() - 1; ++i) {
            if (!((nums[i] % 2) ^ (nums[i + 1] % 2))) {
                return false;
            }
        }
        return true;
    }
};
function isSpecialArray(nums) {
    for (let i = 0; i < nums.length - 1; i++) {
        if (!((nums[i] % 2) ^ (nums[i + 1] % 2))) {
            return false;
        }
    }
    return true;
}
#include <stdbool.h>

bool isSpecialArray(int* nums, int numsSize) {
    for (int i = 0; i < numsSize - 1; i++) {
        if (!((nums[i] % 2) ^ (nums[i + 1] % 2))) {
            return false;
        }
    }
    return true;
}
public class Solution {
    public bool IsSpecialArray(int[] nums) {
        for (int i = 0; i < nums.Length - 1; i++) {
            if (!((nums[i] % 2) ^ (nums[i + 1] % 2))) {
                return false;
            }
        }
        return true;
    }
}

In this Python solution, XOR is used to compare adjacent element parities, returning false if they are the same.

Complexity

Time Complexity: O(n).
Space Complexity: O(1).

Try this approach in the editor

Approach 3: 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.

The time complexity is O(n), where n is the length of the array. The space complexity is $O(1)`.

function isArraySpecial(nums: number[]): boolean {
    for (let i = 1; i < nums.length; ++i) {
        if (nums[i] % 2 === nums[i - 1] % 2) {
            return false;
        }
    }
    return true;
}
func isArraySpecial(nums []int) bool {
	for i, x := range nums[1:] {
		if x%2 == nums[i]%2 {
			return false
		}
	}
	return true
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
Iterative Check

Time Complexity: O(n).
Space Complexity: O(1).

Using XOR for Parity Check

Time Complexity: O(n).
Space Complexity: O(1).

Single Pass–

Complexity analysis

ApproachTimeSpaceWhen to Use
Iterative Parity CheckO(n)O(1)Best general approach. Simple linear scan and easiest to explain in interviews.
XOR Parity CheckO(n)O(1)Useful when applying bit manipulation patterns or optimizing parity checks.

Frequently asked questions

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.

Comments

Now write it yourselfClose this page and solve Special Array I in the editor, without looking.
Practise Special Array I