3152. Special Array II LeetCode Solution

In this guide, you will get 3152. Special Array II LeetCode Solution with the best time and space complexity. The solution to Special Array II problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Special Array II solution in C++
Special Array II solution in Java
Special Array II solution in Python
Additional Resources

3152. Special Array II LeetCode Solution image

Problem Statement of 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:

Input: nums = [3,4,1,2,6], queries = [[0,4]]
Output: [false]
Explanation:
The subarray is [3,4,1,2,6]. 2 and 6 are both even.

Example 2:

Input: nums = [4,3,1,6], queries = [[0,2],[2,3]]
Output: [false,true]
Explanation:

The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
The subarray is [1,6]. There is only one pair: (1,6) and it contains numbers with different parity. So the answer to this query is true.

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

Complexity Analysis

Time Complexity: O(n + q)
Space Complexity: O(n + q)

3152. Special Array II LeetCode Solution in C++

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

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

    for (const vector<int> query : queries) {
      const int from = query[0];
      const int to = query[1];
      ans.push_back(parityIds[from] == parityIds[to]);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

3152. Special Array II LeetCode Solution in Java

class Solution {
  public boolean[] isArraySpecial(int[] nums, int[][] queries) {
    boolean[] ans = new boolean[queries.length];
    // parityIds[i] := the id of the parity group that nums[i] belongs to
    int[] parityIds = new int[nums.length];
    int id = 0;
    parityIds[0] = id;

    for (int i = 1; i < nums.length; ++i) {
      if (nums[i] % 2 == nums[i - 1] % 2)
        ++id;
      parityIds[i] = id;
    }

    for (int i = 0; i < queries.length; ++i) {
      final int from = queries[i][0];
      final int to = queries[i][1];
      ans[i] = parityIds[from] == parityIds[to];
    }

    return ans;
  }
}
// code provided by PROGIEZ

3152. Special Array II LeetCode Solution in Python

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

    for a, b in itertools.pairwise(nums):
      if a % 2 == b % 2:
        id += 1
      parityIds.append(id)

    for _from, to in queries:
      ans.append(parityIds[_from] == parityIds[to])

    return ans
 # code by PROGIEZ