Special Array II

Leetcode Problem:

• Special Array II

Summary

• Check if every pair of adjacent elements in an array contains numbers with different parity.

Approach

• Use a prefix sum array to store the parity of each element in the array
• Then for each query, check if the difference between the parity at the end and start indices is equal to the number of elements in the query
• If it is, the subarray is special.

Complexity

• O(n + q) where n is the size of the array and q is the number of queries.

Explanation

• The solution uses a prefix sum array to store the parity of each element in the array
• The parity is 1 if the number is odd and 0 if the number is even
• The prefix sum array is updated by adding 1 to the parity if the current number is even and the previous number is odd, or if the current number is odd and the previous number is even
• Then for each query, the difference between the parity at the end and start indices is calculated
• If the difference is equal to the number of elements in the query, the subarray is special
• Otherwise, it is not special.

Solution Code:

class Solution {
public:
    vector isArraySpecial(vector& nums, vector>& queries) {
        vector ans;
        vector memo;
        memo.push_back(1);
        for(int i = 1 ; i < nums.size(); i++){
            int num = memo.back();
            if(nums[i] %2 == nums[i-1] %2){
                memo.push_back(num);
            } else{
                memo.push_back(num+1);
            }
        }
        for(int i =  0; i < queries.size(); i++){
            int a = queries[i][0];
            int b = queries[i][1];
            if(b- a == memo[b] - memo[a]){
                ans.push_back(true);
            } else {
                ans.push_back(false);
            }
        }
        return ans;
    }
};