3152.Special Array II.md

Difficulty	Source	Tags
Medium	Daily-Question (POTD 09-Dec)	Array Binary Search Prefix Sum

🚀 3152 - Special Array II 🧠

Problem Link:

LeetCode - Special Array II

💡 Problem Breakdown:

You are given an array nums and a list of queries where each query contains two integers [fromi, toi]. Your task is to determine if the subarray nums[fromi..toi] is special, where a special array is defined as:

• Special Array: An array where every pair of adjacent elements has different parity. That is, one element is even and the next is odd or vice versa.

For each query, return true if the subarray from nums[fromi] to nums[toi] is special, otherwise return false.

🔍 Example Walkthrough:

Example 1:

Input:

nums = [3, 4, 1, 2, 6], queries = [[0, 4]]

Output:
[false]

Explanation:
The subarray is [3, 4, 1, 2, 6]. Elements 2 and 6 are both even, so the subarray is not special.

Example 2:

Input:

nums = [4, 3, 1, 6], queries = [[0, 2], [2, 3]]

Output:
[false, true]

Explanation:
For query [0, 2], the subarray is [4, 3, 1]. Elements 3 and 1 are both odd, so the answer is false.
For query [2, 3], the subarray is [1, 6]. The elements 1 and 6 have different parity (odd and even), so the answer is true.

Constraints:

• $1 <= nums.length <= 10^5$
• $1 <= nums[i] <= 10^5$
• $1 <= queries.length <= 10^5$
• queries[i].length == 2
• 0 <= queries[i][0] <= queries[i][1] <= nums.length - 1

🎯 My Approach:

The goal is to check if each subarray for the given queries is special. A direct approach would involve checking each subarray for every query, which can be inefficient given the constraints. Here's an optimized approach:

Optimized Approach:

1. Preprocessing the Parity of Elements:

   • First, we preprocess the array to check the parity (even or odd) of each element.
   • Create an array parity where parity[i] = 0 if nums[i] is even and parity[i] = 1 if nums[i] is odd.

2. Precompute Differences:

   • Precompute a difference array where each element diff[i] stores whether the parity of nums[i] differs from nums[i+1]. If it differs, it’s set to 1; otherwise, 0.

3. Answering Queries Efficiently:

   • For each query [fromi, toi], simply check if all the elements between fromi and toi in the diff array are 1. If they are, the subarray is special.

By preprocessing the diff array in advance, we can answer each query in constant time.

🕒 Time Complexity:

• Preprocessing:
  The preprocessing step involves creating the parity array and the diff array, which takes O(n), where n is the length of the nums array.

• Query Answering:
  Each query can be answered in O(1) time by checking the relevant segment of the diff array. Given that there can be up to q queries, the overall time complexity for answering queries is O(q).

Thus, the total time complexity is:

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

Space Complexity:

• O(n) for storing the parity and diff arrays.

📝 Solution Code

Code (C):

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
bool* isArraySpecial(int* nums, int numsSize, int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
    *returnSize = queriesSize;
    bool* result = (bool*)malloc(queriesSize * sizeof(bool));
    int* d = (int*)malloc(numsSize * sizeof(int));
    for (int i = 0; i < numsSize; ++i) {
        d[i] = i;
    }
    for (int i = 1; i < numsSize; ++i) {
        if ((nums[i] % 2) != (nums[i - 1] % 2)) {
            d[i] = d[i - 1];
        }
    }
    for (int i = 0; i < queriesSize; ++i) {
        int f = queries[i][0];
        int t = queries[i][1];
        result[i] = (d[t] <= f);
    }
    free(d);

    return result;
}

Code (C++)

class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> d(n);
        iota(d.begin(), d.end(), 0);
        for (int i = 1; i < n; ++i) {
            if (nums[i] % 2 != nums[i - 1] % 2) {
                d[i] = d[i - 1];
            }
        }
        vector<bool> ans;
        for (auto& q : queries) {
            ans.push_back(d[q[1]] <= q[0]);
        }
        return ans;
    }
};

Code (Java)

class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] d = new int[n];
        for (int i = 1; i < n; ++i) {
            if (nums[i] % 2 != nums[i - 1] % 2) {
                d[i] = d[i - 1];
            } else {
                d[i] = i;
            }
        }
        int m = queries.length;
        boolean[] ans = new boolean[m];
        for (int i = 0; i < m; ++i) {
            ans[i] = d[queries[i][1]] <= queries[i][0];
        }
        return ans;
    }
}

Code (Python)

class Solution:
    def isArraySpecial(self, nums: List[int], queries: List[List[int]]) -> List[bool]:
        n = len(nums)
        d = list(range(n))
        for i in range(1, n):
            if nums[i] % 2 != nums[i - 1] % 2:
                d[i] = d[i - 1]
        return [d[t] <= f for f, t in queries]

Code (Rust)

impl Solution {
    pub fn is_array_special(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<bool> {
        let n = nums.len();
        let mut d = (0..n).collect::<Vec<usize>>();

        for i in 1..n {
            if nums[i] % 2 != nums[i - 1] % 2 {
                d[i] = d[i - 1];
            }
        }
        queries
            .iter()
            .map(|query| {
                let f = query[0] as usize;
                let t = query[1] as usize;
                d[t] <= f
            })
            .collect()
    }
}

🎯 Contribute or Ask Questions:

For more discussions, questions, or help with the solution, feel free to reach out on LinkedIn: Connect with Me!.

Enjoying the Solution?

If this helped you, please star this repo to support the efforts and keep it growing!