Minimum removals to balance array

Array Binary Search Sliding Window Sorting

47.9% acceptance

Feb 25, 2026

604

You are given an integer array nums and an integer k. An array is considered balanced if the value of its maximum element is at most k times the minimum element. You may remove any number of elements from nums without making it empty. Return the minimum number of elements to remove so that the remaining array is balanced. Note: An array of size 1 is considered balanced as its maximum and minimum are equal.

Solution

Rust

Time O(n²)

Space O(1)

LeetCode

solution.rs

impl Solution {
  pub fn min_removal(mut nums: Vec<i32>, k: i32) -> i32 {
    nums.sort_unstable();
    let n = nums.len();
    let k = k as i64;
    // Sorted: nums[0] <= ... <= nums[n-1]
    // We pick a contiguous subarray nums[l..=r] (sorted) to keep.
    // Condition: nums[r] <= k * nums[l]
    // We want to maximize (r - l + 1), minimize removals = n - (r - l + 1).
    // For each l, binary search for the largest r such that nums[r] <= k * nums[l].
    let mut max_keep = 1usize;
    let mut left = 0usize;
    for l in 0..n {
      // Find largest r in [l, n-1] with nums[r] <= k * nums[l]
      let limit = k * nums[l] as i64;
      // Binary search
      let mut lo = l;
      let mut hi = n - 1;
      while lo < hi {
        let mid = (lo + hi + 1) / 2;
        if nums[mid] as i64 <= limit {
          lo = mid;
        } else {
          hi = mid - 1;
        }
      }
      let keep = lo - l + 1;
      if keep > max_keep {
        max_keep = keep;
        left = l;
      }
    }
    let _ = left;
    (n - max_keep) as i32
  }
}