3152. Special Array II

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:

Example 2:

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

Approach 01:

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        vector<bool> results;
        int parityGroupId = 0;
        // parityGroupIds[i] := the group ID of the parity that nums[i] belongs to
        vector<int> parityGroupIds = {parityGroupId};

        for (int i = 1; i < nums.size(); ++i) {
            if (nums[i] % 2 == nums[i - 1] % 2){
                ++parityGroupId;
            }
            parityGroupIds.push_back(parityGroupId);
        }

        for (const vector<int> query : queries) {
            const int startIndex = query[0];
            const int endIndex = query[1];
            results.push_back(parityGroupIds[startIndex] == parityGroupIds[endIndex]);
        }

        return results;
    }
};

class Solution:
    def isArraySpecial(self, nums: list[int], queries: list[list[int]]) -> list[bool]:
        results = []
        parityGroupId = 0
        # parityGroupIds[i] := the group ID of the parity that nums[i] belongs to
        parityGroupIds = [parityGroupId]

        for i in range(1, len(nums)):
            if nums[i] % 2 == nums[i - 1] % 2:
                parityGroupId += 1
            parityGroupIds.append(parityGroupId)

        for query in queries:
            startIndex = query[0]
            endIndex = query[1]
            results.append(parityGroupIds[startIndex] == parityGroupIds[endIndex])

        return results

Time Complexity

• Assigning Parity Group IDs:
  • The array nums is traversed once to compute the parity group IDs for all elements.
  • This step takes \(O(n)\), where \(n\) is the size of the array.
• Processing Queries:
  • Each query checks whether two indices belong to the same parity group by comparing their IDs.
  • This involves a single comparison for each query and takes \(O(1)\) per query.
  • For \(q\) queries, this step takes \(O(q)\).
• Overall Time Complexity:

  The total time complexity is \(O(n + q)\), where \(n\) is the size of the array and \(q\) is the number of queries.

Space Complexity

• Parity Group IDs:
  • The vector parityGroupIds is used to store the parity group ID for each element in the array.
  • This requires \(O(n)\) space, where \(n\) is the size of the array.
• Results:
  • The vector results stores the boolean result for each query.
  • This requires \(O(q)\) space, where \(q\) is the number of queries.
• Other Variables:
  • Variables like parityGroupId and loop variables require \(O(1)\) space.
• Overall Space Complexity:

  The total space complexity is \(O(n + q)\), dominated by the storage for parity group IDs and results.