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:

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:

1. The subarray is [4,3,1]. 3 and 1 are both odd. So the answer to this query is false.
2. 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

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;
      }
  };

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;
      }
  }

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]
          
          ans = []
          for q in queries:
              ans.append(d[q[1]] <= q[0])
          
          return ans