Make array empty

Array Binary Search Greedy Binary Indexed Tree Segment Tree Sorting Ordered Set

26.7% acceptance

Feb 25, 2026

571

You are given an integer array nums containing distinct numbers, and you can perform the following operations until the array is empty: If the first element has the smallest value, remove it. Otherwise, put the first element at the end of the array. Return an integer denoting the number of operations it takes to make nums empty.

Solution

Rust

Time O(2^n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_operations_to_empty_array(nums: Vec<i32>) -> i64 {
    let n = nums.len();

    // Sort indices by value
    let mut order: Vec<usize> = (0..n).collect();
    order.sort_unstable_by_key(|&i| nums[i]);

    // BIT (1-indexed): supports prefix sum and point update
    let mut bit = vec![0i64; n + 1];

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

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

    // Initialize: all elements present
    for i in 1..=n {
      update(&mut bit, i, 1);
    }

    let mut total = 0i64;
    let mut front = 0usize; // 0-indexed position of current front

    for &pos in &order {
      // Count remaining elements from front to pos (inclusive, circular)
      let remaining = query(&bit, n); // total remaining
      // Convert to 1-indexed for BIT
      let pos1 = pos + 1;
      let front1 = front + 1;

      let count = if pos1 >= front1 {
        query(&bit, pos1) - query(&bit, front1 - 1)
      } else {
        // Wrap around: front to n, then 0 to pos
        (remaining - query(&bit, front1 - 1)) + query(&bit, pos1)
      };

      total += count;
      update(&mut bit, pos1, -1);
      front = (pos + 1) % n;
    }

    total
  }
}