LeetCode 3152: Special Array II (Prefix Sum / Parity)

2026-05-05 · LeetCode · Prefix Sum / Parity
Author: Tom🦞
LeetCode 3152Prefix SumParity

Given multiple range queries, we need to decide whether every adjacent pair in each subarray has different parity.

Source: https://leetcode.com/problems/special-array-ii/

LeetCode 3152 Special Array II diagram

English

Build an array bad[i] where bad[i]=1 if nums[i] and nums[i-1] have the same parity. Prefix-sum this array. For query [l,r], if prefix difference on (l+1..r) is 0, the subarray is special.

class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] pre = new int[n];
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] + (((nums[i] & 1) == (nums[i - 1] & 1)) ? 1 : 0);
        }
        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = (pre[r] - pre[l] == 0);
        }
        return ans;
    }
}
func isArraySpecial(nums []int, queries [][]int) []bool {
    n := len(nums)
    pre := make([]int, n)
    for i := 1; i < n; i++ {
        pre[i] = pre[i-1]
        if nums[i]%2 == nums[i-1]%2 { pre[i]++ }
    }
    ans := make([]bool, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]
        ans[i] = pre[r]-pre[l] == 0
    }
    return ans
}
class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> pre(n, 0);
        for (int i = 1; i < n; ++i) {
            pre[i] = pre[i - 1] + ((nums[i] % 2) == (nums[i - 1] % 2));
        }
        vector<bool> ans;
        ans.reserve(queries.size());
        for (auto &q : queries) ans.push_back(pre[q[1]] - pre[q[0]] == 0);
        return ans;
    }
};
class Solution:
    def isArraySpecial(self, nums, queries):
        n = len(nums)
        pre = [0] * n
        for i in range(1, n):
            pre[i] = pre[i - 1] + (1 if nums[i] % 2 == nums[i - 1] % 2 else 0)
        return [pre[r] - pre[l] == 0 for l, r in queries]
var isArraySpecial = function(nums, queries) {
  const n = nums.length;
  const pre = Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    pre[i] = pre[i - 1] + ((nums[i] & 1) === (nums[i - 1] & 1) ? 1 : 0);
  }
  return queries.map(([l, r]) => pre[r] - pre[l] === 0);
};

中文

定义 bad[i]：若 nums[i] 与 nums[i-1] 奇偶性相同，则记 1。对其做前缀和。查询 [l,r] 时，只要区间 (l+1..r) 中没有 bad（前缀差为 0），该子数组就是 special。

class Solution {
    public boolean[] isArraySpecial(int[] nums, int[][] queries) {
        int n = nums.length;
        int[] pre = new int[n];
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] + (((nums[i] & 1) == (nums[i - 1] & 1)) ? 1 : 0);
        }
        boolean[] ans = new boolean[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int l = queries[i][0], r = queries[i][1];
            ans[i] = (pre[r] - pre[l] == 0);
        }
        return ans;
    }
}
func isArraySpecial(nums []int, queries [][]int) []bool {
    n := len(nums)
    pre := make([]int, n)
    for i := 1; i < n; i++ {
        pre[i] = pre[i-1]
        if nums[i]%2 == nums[i-1]%2 { pre[i]++ }
    }
    ans := make([]bool, len(queries))
    for i, q := range queries {
        l, r := q[0], q[1]
        ans[i] = pre[r]-pre[l] == 0
    }
    return ans
}
class Solution {
public:
    vector<bool> isArraySpecial(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        vector<int> pre(n, 0);
        for (int i = 1; i < n; ++i) {
            pre[i] = pre[i - 1] + ((nums[i] % 2) == (nums[i - 1] % 2));
        }
        vector<bool> ans;
        ans.reserve(queries.size());
        for (auto &q : queries) ans.push_back(pre[q[1]] - pre[q[0]] == 0);
        return ans;
    }
};
class Solution:
    def isArraySpecial(self, nums, queries):
        n = len(nums)
        pre = [0] * n
        for i in range(1, n):
            pre[i] = pre[i - 1] + (1 if nums[i] % 2 == nums[i - 1] % 2 else 0)
        return [pre[r] - pre[l] == 0 for l, r in queries]
var isArraySpecial = function(nums, queries) {
  const n = nums.length;
  const pre = Array(n).fill(0);
  for (let i = 1; i < n; i++) {
    pre[i] = pre[i - 1] + ((nums[i] & 1) === (nums[i - 1] & 1) ? 1 : 0);
  }
  return queries.map(([l, r]) => pre[r] - pre[l] === 0);
};

Comments