Special array ii

Array Binary Search Prefix Sum

45.8% acceptance

Feb 24, 2026

915

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn is_array_special(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<bool> {
    let n = nums.len();
    // prefix[i] = # of bad pairs at indices 0..i-1
    // bad pair at index j: nums[j] and nums[j+1] have same parity
    let mut prefix = vec![0i32; n];
    for i in 1..n {
      prefix[i] = prefix[i - 1] + if nums[i - 1] % 2 == nums[i] % 2 { 1 } else { 0 };
    }
    // query [from, to]: bad pairs at indices from..to-1 = prefix[to] - prefix[from]
    queries
      .iter()
      .map(|q| {
        let from = q[0] as usize;
        let to = q[1] as usize;
        prefix[to] - prefix[from] == 0
      })
      .collect()
  }
}