Peaks in array

Array Binary Indexed Tree Segment Tree

27.2% acceptance

Feb 24, 2026

142

A peak in an array arr is an element that is greater than its previous and next element in arr. You are given an integer array nums and a 2D integer array queries. You have to process queries of two types: queries[i] = [1, li, ri], determine the count of peak elements in the subarray nums[li..ri]. queries[i] = [2, indexi, vali], change nums[indexi] to vali. Return an array answer containing the results of the queries of the first type in order. Notes: The first and the last element of an array or a subarray cannot be a peak.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_of_peaks(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
    let n = nums.len();
    let mut nums = nums;

    // BIT (Fenwick tree) over "is_peak" array for indices 1..n-2
    // is_peak[i] = 1 if nums[i-1] < nums[i] > nums[i+1], else 0
    let mut bit = vec![0i32; n + 1];

    let is_peak = |nums: &[i32], i: usize| -> i32 {
      if i == 0 || i + 1 >= nums.len() {
        0
      } else if nums[i] > nums[i - 1] && nums[i] > nums[i + 1] {
        1
      } else {
        0
      }
    };

    let bit_update = |bit: &mut Vec<i32>, mut i: usize, delta: i32| {
      while i < bit.len() {
        bit[i] += delta;
        i += i & i.wrapping_neg();
      }
    };

    let bit_query = |bit: &Vec<i32>, mut i: usize| -> i32 {
      let mut s = 0;
      while i > 0 {
        s += bit[i];
        i -= i & i.wrapping_neg();
      }
      s
    };

    // 1-indexed BIT: position i in BIT corresponds to index i in nums
    for i in 1..n - 1 {
      let v = is_peak(&nums, i);
      if v == 1 {
        bit_update(&mut bit, i + 1, 1); // BIT is 1-indexed so position i+1 for nums[i]
      }
    }

    let mut result = Vec::new();

    for q in &queries {
      match q[0] {
        1 => {
          let l = q[1] as usize;
          let r = q[2] as usize;
          if r - l < 2 {
            result.push(0);
          } else {
            // Count peaks in range (l+1)..=(r-1) in nums indices
            // BIT positions: nums[i] -> BIT pos i+1
            // We want sum over i in [l+1, r-1], BIT positions [l+2, r]
            let ans = bit_query(&bit, r) - bit_query(&bit, l + 1);
            result.push(ans);
          }
        }
        2 => {
          let idx = q[1] as usize;
          let val = q[2];
          nums[idx] = val;
          // Update peaks at idx-1, idx, idx+1
          let lo = if idx > 0 { idx - 1 } else { 0 };
          let hi = if idx + 1 < n { idx + 1 } else { n - 1 };
          for i in lo..=hi {
            if i == 0 || i + 1 >= n {
              continue;
            }
            let old_in_bit = bit_query(&bit, i + 1) - bit_query(&bit, i);
            let new_val = is_peak(&nums, i);
            let delta = new_val - old_in_bit;
            if delta != 0 {
              bit_update(&mut bit, i + 1, delta);
            }
          }
        }
        _ => {}
      }
    }

    result
  }
}