# Special Array I
**Difficulty:** EASY
[External](https://leetcode.com/problems/special-array-i)
Canonical: https://scaleengineer.com/dsa/problems/special-array-i
**Data structures:** Array
**Companies:** [National Payments Corporation of India](https://scaleengineer.com/companies/national-payments-corporation-of-india)
---
## Problem
An array is considered **special** if the _parity_ of every pair of adjacent elements is different. In other words, one element in each pair **must** be even, and the other **must** be odd.

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`

# Approaches
## Two-Pass with Extra Space
This approach involves two main steps. First, it transforms the input array of numbers into an array of their parities (0 for even, 1 for odd). Then, it iterates through this new parity array to check if any adjacent elements are the same. While correct, this method is less efficient due to the extra space required for the parity array and the two separate loops.
**Time:** O(n), where n is the length of the array. The first loop runs n times, and the second loop runs n-1 times. The total time is O(n + n) = O(n). · **Space:** O(n), where n is the length of the array. This is due to the extra `parities` array we create.
**Pros:** Conceptually simple, as it separates concerns (calculating parity vs. checking adjacency).; Easy to understand and debug.
**Cons:** Inefficient in terms of space, as it requires an auxiliary array of size O(n).; Less time-efficient as it requires two separate passes over the data, whereas one is sufficient.
### Explanation
The core idea is to separate the process of determining parity from the process of checking for adjacent violations.

- We start by creating an auxiliary array, let's call it `parities`, with the same length as the input `nums` array.
- We then perform the first pass: iterate through `nums` from the first to the last element. For each number `nums[i]`, we compute its parity using the modulo operator (`nums[i] % 2`) and store the result (0 or 1) in the corresponding position `parities[i]`.
- After the first pass, the `parities` array contains a sequence of 0s and 1s representing the parity of each number in the original array.
- The second pass involves iterating through the `parities` array from the first element up to the second-to-last element (`i` from 0 to `n-2`).
- In each step of this second loop, we compare `parities[i]` with `parities[i+1]`. If we find any pair where `parities[i]` is equal to `parities[i+1]`, it means two adjacent numbers in the original array had the same parity. In this case, the array is not special, and we can immediately return `false`.
- If the second loop completes without finding any such pair, it confirms that all adjacent elements have different parities, and thus the array is special. We then return `true`.

```java
class Solution {
    public boolean isSpecialArray(int[] nums) {
        if (nums.length <= 1) {
            return true;
        }
        
        int n = nums.length;
        int[] parities = new int[n];
        
        // First pass: compute parities
        for (int i = 0; i < n; i++) {
            parities[i] = nums[i] % 2;
        }
        
        // Second pass: check adjacent parities
        for (int i = 0; i < n - 1; i++) {
            if (parities[i] == parities[i+1]) {
                return false;
            }
        }
        
        return true;
    }
}
```
### Algorithm
- 1. If the length of `nums` is 1 or less, return `true`.
- 2. Create a new integer array `parities` of the same size as `nums`.
- 3. Iterate through `nums` from `i = 0` to `nums.length - 1`.
- 4. In each iteration, calculate `nums[i] % 2` and store it in `parities[i]`.
- 5. Iterate through `parities` from `i = 0` to `parities.length - 2`.
- 6. In each iteration, check if `parities[i] == parities[i+1]`.
- 7. If they are equal, return `false`.
- 8. If the loop finishes, return `true`.

## Single-Pass Iteration
This is the most efficient approach. It involves a single loop through the array, checking the parity of each adjacent pair of elements on the fly. If any pair has the same parity, we can immediately conclude the array is not special and return `false`. If the loop completes without finding such a pair, the array is special.
**Time:** O(n), where n is the length of the array. In the worst case, we iterate through all n-1 adjacent pairs. · **Space:** O(1), as we only use a few variables for the loop counter and comparisons, regardless of the input size.
**Pros:** Optimal time complexity, as it only requires a single pass through the array.; Optimal space complexity, using only a constant amount of extra space.; Early exit: the function returns as soon as a violation is found, which can save computation on large arrays that are not special.
**Cons:** No significant cons; this is the standard and most efficient way to solve this problem.
### Explanation
This optimized method avoids the need for extra space and a second pass by combining the parity calculation and the adjacency check into a single loop.

- We handle the base case first: if the array has one or zero elements, it's trivially special, so we return `true`.
- We then iterate through the array from the first element up to the second-to-last element (i.e., from index `i = 0` to `nums.length - 2`). This range is chosen because we need to compare each element `nums[i]` with its next neighbor `nums[i+1]`.
- Inside the loop, for each index `i`, we check if the parity of `nums[i]` is the same as the parity of `nums[i+1]`. This can be done by comparing the results of the modulo 2 operation: `(nums[i] % 2) == (nums[i+1] % 2)`.
- If this condition is true for any `i`, it means we've found two adjacent elements with the same parity. The array does not meet the "special" criteria, so we can stop processing and return `false` immediately.
- If the loop finishes without ever triggering the `return false` statement, it means that for every `i`, `nums[i]` and `nums[i+1]` had different parities. Therefore, the array is special, and we return `true` after the loop.

```java
class Solution {
    public boolean isSpecialArray(int[] nums) {
        // An array with 0 or 1 elements is special.
        if (nums.length <= 1) {
            return true;
        }
        
        // Iterate through adjacent pairs.
        for (int i = 0; i < nums.length - 1; i++) {
            // Check if the parity of adjacent elements is the same.
            if ((nums[i] % 2) == (nums[i+1] % 2)) {
                // If they have the same parity, the array is not special.
                return false;
            }
        }
        
        // If the loop completes, all adjacent pairs have different parities.
        return true;
    }
}
```
### Algorithm
- 1. Iterate through the `nums` array from `i = 0` to `nums.length - 2`.
- 2. For each `i`, compare the parity of `nums[i]` and `nums[i+1]` using the modulo operator: `(nums[i] % 2) == (nums[i+1] % 2)`.
- 3. If the parities are the same, the condition is violated. Return `false` immediately.
- 4. If the loop completes without finding any violation, it means all adjacent pairs have different parities. Return `true`.

# Solutions
### Java

```java
class Solution {
public
  boolean isArraySpecial(int[] nums) {
    for (int i = 1; i < nums.length; ++i) {
      if (nums[i] % 2 == nums[i - 1] % 2) {
        return false;
      }
    }
    return true;
  }
}

```

### CPP

```cpp
class Solution {
public:
  bool isArraySpecial(vector<int> &nums) {
    for (int i = 1; i < nums.size(); ++i) {
      if (nums[i] % 2 == nums[i - 1] % 2) {
        return false;
      }
    }
    return true;
  }
};

```

### Python

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

```