Special Array II
Source: leetcode
Difficulty: Medium
Tags: array, binary-search, prefix-sum

An array is considered **special** if every pair of its adjacent elements contains two numbers with different parity.


You are given an array of integer `nums` and a 2D integer matrix `queries`, where for `queries[i] = [fromi, toi]` your task is to check that subarray `nums[fromi..toi]` is **special** or not.


Return an array of booleans `answer` such that `answer[i]` is `true` if `nums[fromi..toi]` is special.


 


**Example 1:**



**Input:** nums \= \[3,4,1,2,6], queries \= \[\[0,4]]


**Output:** \[false]


**Explanation:**


The subarray is `[3,4,1,2,6]`. 2 and 6 are both even.



**Example 2:**



**Input:** nums \= \[4,3,1,6], queries \= \[\[0,2],\[2,3]]


**Output:** \[false,true]


**Explanation:**


1. The subarray is `[4,3,1]`. 3 and 1 are both odd. So the answer to this query is `false`.
2. The subarray is `[1,6]`. There is only one pair: `(1,6)` and it contains numbers with different parity. So the answer to this query is `true`.



 


**Constraints:**


- `1 <= nums.length <= 105`
- `1 <= nums[i] <= 105`
- `1 <= queries.length <= 105`
- `queries[i].length == 2`
- `0 <= queries[i][0] <= queries[i][1] <= nums.length - 1`




C++ solution:
class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);

        int n = nums.size();
        int num_queries = queries.size();
        vector<bool> result(num_queries, false);
        vector<int> arr(n, 0);
        
        for (int i = 1; i < n; i++) {
            arr[i] = arr[i - 1] + (nums[i] % 2 == nums[i - 1] % 2);
        }

        for (int i = 0; i < num_queries; i++) {
            result[i] = (arr[queries[i][1]] - arr[queries[i][0]] == 0);
        }

        return result;
    }
};

Go solution:
func isArraySpecial(nums []int, queries [][]int) []bool {
    n := len(nums)
    prefixSum := make([]int, n)

    // Step 1: Compute prefixSum
    for i := 1; i < n; i++ {
        prefixSum[i] = prefixSum[i-1]
        if (nums[i]%2 == 0 && nums[i-1]%2 != 0) || (nums[i]%2 != 0 && nums[i-1]%2 == 0) {
            prefixSum[i]++
        }
    }

    // Step 2: Process queries
    result := []bool{}
    for _, query := range queries {
        left, right := query[0], query[1]
        totalPairs := right - left
        validPairs := prefixSum[right] - prefixSum[left]
        result = append(result, validPairs == totalPairs)
    }

    return result
}

Java solution:
class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] prefix = new int[n]; // Prefix array to count special pairs
        boolean[] result = new boolean[queries.length]; // Result array
        
        // Step 1: Build the prefix array
        for (int i = 1; i < n; i++) {
            prefix[i] = prefix[i - 1];
            if ((nums[i - 1] % 2 == 0 && nums[i] % 2 == 0) || 
                (nums[i - 1] % 2 != 0 && nums[i] % 2 != 0)) {
                prefix[i]++;
            }
        }

        // Step 2: Process each query
        for (int i = 0; i < queries.length; i++) {
            int left = queries[i][0];
            int right = queries[i][1];
            
            // Calculate the number of special pairs in the range
            int specialCount = prefix[right] - (left > 0 ? prefix[left] : 0);
            
            // If no special pairs, the result is true; otherwise, false
            result[i] = (specialCount == 0);
        }

        return result;
    }
}

JavaScript solution:
/**
 * @param {number[]} nums
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var isArraySpecial = function(nums, queries) {
    const n = nums.length;
    const prefix = Array(n).fill(0);  // Initialize prefix array

    // Build the prefix array to count special pairs
    for (let i = 1; i < n; i++) {
        prefix[i] = prefix[i - 1];
        if ((nums[i - 1] % 2 === 0 && nums[i] % 2 === 0) || 
            (nums[i - 1] % 2 !== 0 && nums[i] % 2 !== 0)) {
            prefix[i]++;
        }
    }

    const result = [];

    // Process each query
    for (let i = 0; i < queries.length; i++) {
        const [left, right] = queries[i];
        const specialCount = prefix[right] - (left > 0 ? prefix[left] : 0);
        result.push(specialCount === 0);
    }

    return result;
};

Python solution:
class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        

        parity = [0 for _ in range(len(nums))]

        for i in range(1, len(nums)):

            if(nums[i] % 2 == nums[i-1] % 2):
                parity[i] = parity[i-1] + 1
            else:
                parity[i] = parity[i-1]
        
        result = []
        for i, j in queries:
            result.append(True if parity[j] == parity[i] else False)
        
        return result

Ruby solution:
# @param {Integer[]} nums
# @param {Integer[][]} queries
# @return {Boolean[]}
def is_array_special(nums, queries)
    n = nums.length
    prefix = Array.new(n, 0)  # Initialize prefix array
    
    # Build the prefix array to count special pairs
    for i in 1...n
        prefix[i] = prefix[i - 1]
        if (nums[i - 1] % 2 == 0 && nums[i] % 2 == 0) || (nums[i - 1] % 2 != 0 && nums[i] % 2 != 0)
            prefix[i] += 1
        end
    end

    result = []  # Result array

    # Process each query
    queries.each do |query|
        left, right = query
        special_count = prefix[right] - (left > 0 ? prefix[left] : 0)
        result << (special_count == 0)
    end

    result  # Return the result array
end