Skip to content

3152. Special Array II 👍

  • Time: $O(n + q)$
  • Space: $O(n + q)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
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