Count the number of k big indices

Array Binary Search Divide and Conquer Binary Indexed Tree Segment Tree Merge Sort Ordered Set

53.7% acceptance

Mar 31, 2026

113

You are given a 0-indexed integer array nums and a positive integer k. We call an index i k-big if the following conditions are satisfied: There exist at least k different indices idx1 such that idx1 < i and nums[idx1] < nums[i]. There exist at least k different indices idx2 such that idx2 > i and nums[idx2] < nums[i]. Return the number of k-big indices.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn k_big_indices(nums: Vec<i32>, k: i32) -> i32 {
    let n = nums.len();
    let k = k as usize;
    let max_val = *nums.iter().max().unwrap() as usize;
    let sz = max_val + 2;

    fn update(tree: &mut Vec<i32>, mut i: usize) {
      while i < tree.len() {
        tree[i] += 1;
        i += i & i.wrapping_neg();
      }
    }

    fn query(tree: &[i32], mut i: usize) -> i32 {
      let mut s = 0;
      while i > 0 {
        s += tree[i];
        i -= i & i.wrapping_neg();
      }
      s
    }

    let mut left = vec![0i32; n];
    let mut tree = vec![0i32; sz];
    for i in 0..n {
      let v = nums[i] as usize;
      left[i] = if v > 1 { query(&tree, v - 1) } else { 0 };
      update(&mut tree, v);
    }

    let mut right = vec![0i32; n];
    let mut tree = vec![0i32; sz];
    for i in (0..n).rev() {
      let v = nums[i] as usize;
      right[i] = if v > 1 { query(&tree, v - 1) } else { 0 };
      update(&mut tree, v);
    }

    let mut count = 0;
    for i in 0..n {
      if left[i] >= k as i32 && right[i] >= k as i32 {
        count += 1;
      }
    }
    count
  }
}