3152. Special Array II

Problem Description

An array is considered special if every pair of its adjacent elements contains two numbers with different parity. You are given an array of integers nums and a 2D integer matrix queries. For each queries[i] = [from_i, to_i], your task is to check if the subarray nums[from_i..to_i] is special or not. Return an array of booleans answer such that answer[i] is true if nums[from_i..to_i] is special.

Intuition

To determine if a subarray is special, we need to ensure that every pair of adjacent elements within the subarray have different parity (one even, one odd).

The implemented solution uses an auxiliary array d where d[i] holds the leftmost position of a subarray that is special starting from the index i. Initially, set d[i] = i for all positions, meaning each position is special by itself. As we traverse through the nums array, if two consecutive elements, nums[i] and nums[i-1], have different parities, we update d[i] to be the same as d[i-1], indicating that the special property extends to the left.

For a query [from_i, to_i], the subarray is special if d[to] <= from. This means that we can trace back the special property from position to to a position at or before from, confirming the entire queried subarray maintains the special property.

Learn more about Binary Search and Prefix Sum patterns.

Solution Approach

In the solution, we employ an auxiliary array d to track the leftmost position at which a contiguous subarray starting from any index remains special. Here's how the approach works:

Initialize the Array d:
We start by setting d[i] = i for each index i in the nums array. This initializes each position as its own special subarray.
Traverse the nums Array:
We iterate over the array nums starting from the second element. For each element nums[i], we compare its parity with the previous element nums[i - 1]:
- If nums[i] and nums[i - 1] have different parities (i.e., one is even and the other is odd), then the special property continues from i-1 to i, so we set d[i] = d[i - 1].
Process the Queries:
For each query [from_i, to_i], we check if the subarray nums[from_i..to_i] is special by ensuring the condition d[to_i] <= from_i holds. If it does, the subarray maintains the special property, and we mark this query as true in the result array.

This approach efficiently determines the special property of subarrays using the insights gathered during the single pass over the nums array, minimizing repeated computations for each query.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider the nums array [3, 2, 5, 6, 3] and a list of queries: [[0, 1], [1, 4], [3, 4]].

Initialize the Array d:

Start with d = [0, 1, 2, 3, 4], where each position represents itself as a special subarray.
Traverse the nums Array:
- For i = 1: Compare nums[1] = 2 and nums[0] = 3.
  - Different parities (2 even, 3 odd), set d[1] = d[0] = 0.
- For i = 2: Compare nums[2] = 5 and nums[1] = 2.
  - Different parities (5 odd, 2 even), set d[2] = d[1] = 0.
- For i = 3: Compare nums[3] = 6 and nums[2] = 5.
  - Different parities (6 even, 5 odd), set d[3] = d[2] = 0.
- For i = 4: Compare nums[4] = 3 and nums[3] = 6.
  - Different parities (3 odd, 6 even), set d[4] = d[3] = 0.
Updated d = [0, 0, 0, 0, 0].
Process the Queries:
- Query [0, 1]: Check d[1] <= 0.
  - d[1] = 0, so 0 <= 0 is true. Subarray nums[0..1] is special.
- Query [1, 4]: Check d[4] <= 1.
  - d[4] = 0, so 0 <= 1 is true. Subarray nums[1..4] is special.
- Query [3, 4]: Check d[4] <= 3.
  - d[4] = 0, so 0 <= 3 is true. Subarray nums[3..4] is special.

The result for these queries would be [true, true, true].

Solution Implementation

1from typing import List
2
3class Solution:
4    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
5        n = len(nums)  # Get the length of the nums list
6        d = list(range(n))  # Initialize a list d with values from 0 to n-1
7
8        # Iterate through the nums list starting from index 1
9        for i in range(1, n):
10            # Check if the current element and the previous element have different parity
11            if nums[i] % 2 != nums[i - 1] % 2:
12                # If they have different parity, assign the current element's index to the previous
13                d[i] = d[i - 1]
14
15        # For each query (f, t) in queries, determine if the array is special
16        return [d[t] <= f for f, t in queries]
17

1class Solution {
2    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
3        int n = nums.length; // Length of the input array
4        int[] d = new int[n]; // Array to store indices or segment starts
5      
6        // Fill the 'd' array based on even/odd condition
7        for (int i = 1; i < n; ++i) {
8            // If the current number has a different parity (even/odd) than the previous
9            if (nums[i] % 2 != nums[i - 1] % 2) {
10                d[i] = d[i - 1]; // Continue with the previous segment
11            } else {
12                d[i] = i; // Start a new segment from the current index
13            }
14        }
15      
16        int m = queries.length; // Number of queries
17        boolean[] ans = new boolean[m]; // Array to store answers for each query
18      
19        for (int i = 0; i < m; ++i) {
20            int start = queries[i][0]; // Start index of the current query
21            int end = queries[i][1]; // End index of the current query
22            // Check if the segment starts before or at the 'start' index
23            ans[i] = d[end] <= start;
24        }
25      
26        return ans; // Return the results array
27    }
28}
29

1#include <vector>
2#include <numeric> // For iota function
3
4class Solution {
5public:
6    // Function to determine if a subarray between indices [0, q[1]] in nums is "special"
7    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
8        int n = nums.size();            // Get the size of the nums array
9        vector<int> d(n);               // Create a vector to store segment indices
10        std::iota(d.begin(), d.end(), 0); // Initialize d with [0, 1, 2, ..., n-1]
11
12        // Determine segments in the nums array
13        for (int i = 1; i < n; ++i) {
14            // Check if there's a parity change between nums[i] and nums[i-1]
15            if (nums[i] % 2 != nums[i - 1] % 2) {
16                d[i] = d[i - 1]; // Merge segments when there's no change in parity
17            }
18        }
19
20        vector<bool> ans; // Vector to store the results for each query
21        for (auto& query : queries) {
22            // Check if the segment index at query[1] is less than or equal to query[0]
23            ans.push_back(d[query[1]] <= query[0]);
24        }
25
26        return ans; // Return the results for all queries
27    }
28};
29

1// Function to check if queries find a "special" interval
2function isArraySpecial(nums: number[], queries: number[][]): boolean[] {
3    const n = nums.length; // Length of the input array
4    // Initialize an array to store "special" indices, starting with identity mapping
5    const d: number[] = Array.from({ length: n }, (_, i) => i);
6
7    // Traverse through the nums array starting from the second element
8    for (let i = 1; i < n; ++i) {
9        // Check if the current and previous element have different odd/even status
10        if (nums[i] % 2 !== nums[i - 1] % 2) {
11            // If they differ, mark the current index with the previous valid special index
12            d[i] = d[i - 1];
13        }
14    }
15
16    // Map each query to a boolean, checking if d[to] is valid within the from index
17    return queries.map(([from, to]) => d[to] <= from);
18}
19

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the nums list. This complexity arises because the algorithm iterates through the nums list a single time to construct the d list.

The space complexity is also O(n). This is due to the d list, which stores n elements corresponding to the length of the nums list.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Question 1 out of 10

Which of the two traversal algorithms (BFS and DFS) can be used to find whether two nodes are connected?

BFS

DFS

Both

Neither

I don’t know