• Leetcode POTDs

Problem 3152 Special Array II

Problem Statement

Link - Problem 3152

Question

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

Solution

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        vector<bool> ans(queries.size(), false);
        vector<int> prefix(nums.size(), 0);
        prefix[0] = 0;

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

        for (int i = 0; i < queries.size(); i++) {
            vector<int> query = queries[i];
            int start = query[0];
            int end = query[1];

            ans[i] = prefix[end] - prefix[start] == 0;
        }

        return ans;
    }
};

Complexity Analysis

| Algorithm              | Time Complexity | Space Complexity |
| ---------------------- | --------------- | ---------------- |
| Prefix Sum Calculation | O(n + q)        | O(n)             |

Explanation

Intial Thoughts

To determine if a subarray is special, we need to check if every pair of adjacent elements has different parity. This can be approached by creating a prefix array that keeps track of the number of pairs with the same parity. The key is to identify a pattern or a way to efficiently compare the parity of adjacent elements. We can start by examining the given solution and understanding how it utilizes the prefix array to simplify the comparison process. The initial steps should involve analyzing the array and queries to identify any patterns or relationships that can aid in solving the problem. We should also consider how the prefix array is constructed and how it is used to determine if a subarray is special.

Intuitive Analysis

The given solution uses a prefix array to efficiently check if a subarray is special. Intuitively, this approach makes sense because it allows us to avoid comparing every pair of adjacent elements in the subarray. Instead, we can use the prefix array to quickly determine if there are any pairs with the same parity. To further develop our intuition, we can think of the prefix array as a ‘counter’ that keeps track of the number of pairs with the same parity. By comparing the values in the prefix array at different indices, we can quickly determine if a subarray is special. We should also consider how the use of the modulo operator (%) to check parity affects the solution and how it contributes to the efficiency of the approach. Additionally, we can explore how the solution would change if we were to use a different data structure or approach.

1. Intuition

• The problem requires checking if every pair of adjacent elements in a subarray has different parity, which means one is even and the other is odd.
• To solve this efficiently, we need to track the number of pairs with the same parity as we iterate through the array.
• A prefix sum array can be used to store the count of pairs with the same parity up to each index.
• The key insight is that if the difference in the prefix sum between the end and start of a subarray is 0, it means all pairs within that subarray have different parity.
• This approach allows us to answer queries about any subarray in constant time after the initial array processing.
• The time complexity of this solution is O(n + q), where n is the size of the array and q is the number of queries.
• This is because we make a single pass through the array to calculate the prefix sum and then process each query individually.

2. Implementation

• We start by initializing a prefix array of the same length as the input nums array, where prefix[i] will store the count of pairs with the same parity up to index i.
• We iterate through nums from the second element to the end, checking if the current element and the previous one have the same parity using the condition nums[i] % 2 == nums[i - 1] % 2.
• If they have the same parity, we increment the count in prefix[i] by 1 compared to prefix[i - 1], otherwise, we keep the count the same.
• For each query, we extract the start and end indices and check if the difference prefix[end] - prefix[start] is 0, indicating all pairs in the subarray have different parity.
• We store the result of this check in the ans array at the corresponding index.
• Finally, we return the ans array containing the results for all queries.
• The use of prefix array allows for efficient calculation of the result for each query without needing to re-examine the subarray.

Complexity Analysis

Time Complexity:

• The algorithm iterates through the input array nums of size n to calculate the prefix sum, resulting in a time complexity of O(n). It then iterates through the queries array of size q, resulting in an additional time complexity of O(q). Since these operations are performed sequentially, the overall time complexity is O(n + q).
• The dominant operations are the two nested loops: one for calculating the prefix sum and the other for iterating through the queries. Each loop has a linear time complexity.
• The Big O classification of O(n + q) is justified because the algorithm’s running time grows linearly with the size of the input array and the number of queries.

Space Complexity:

• The algorithm uses a prefix sum array prefix of size n to store the cumulative sum of the input array nums, resulting in a space complexity of O(n).
• The use of the prefix array dominates the memory usage, as it requires a separate array of the same size as the input array.
• The space complexity is O(n) because the algorithm only uses a constant amount of additional space to store the input array and the queries, and the size of the prefix sum array grows linearly with the size of the input array.

Proof of correctness

• Special Array II Algorithm
• Direct Proof

Footnote

This question is rated as Medium difficulty.

Hints

Try to split the array into some non-intersected continuous special subarrays.

For each query check that the first and the last elements of that query are in the same subarray or not.