Minimum Removals to Balance Array

medium sorting sliding window two pointers

Problem

Given an integer array nums and an integer k, an array is balanced if its maximum element is at most k times its minimum element (max ≤ k · min). You may remove any number of elements but must leave the array non-empty. Return the minimum number of elements to remove so the rest is balanced. A single element is always balanced.

Inputnums = [2, 1, 5], k = 2

Output1

Remove 5 to get [2, 1]: max = 2, min = 1, and 2 ≤ 1 · 2. One removal.

nums (comma-separated)

def minRemoval(nums, k):
    nums.sort()                       # min/max become window ends
    n = len(nums)
    best = 0                          # largest balanced window size
    i = 0                             # left end of window
    for j in range(n):                # j = right end (current max)
        while nums[j] > k * nums[i]:   # window too spread out
            i += 1                    # shrink from the left
        best = max(best, j - i + 1)   # keep widest valid window
    return n - best                   # remove everything outside it

function minRemoval(nums, k) {
  nums.sort((a, b) => a - b);         // min/max become window ends
  const n = nums.length;
  let best = 0;                       // largest balanced window size
  let i = 0;                          // left end of window
  for (let j = 0; j < n; j++) {       // j = right end (current max)
    while (nums[j] > k * nums[i]) {    // window too spread out
      i++;                            // shrink from the left
    }
    best = Math.max(best, j - i + 1); // keep widest valid window
  }
  return n - best;                    // remove everything outside it
}

int minRemoval(int[] nums, int k) {
    Arrays.sort(nums);                   // min/max become window ends
    int n = nums.length;
    int best = 0;                        // largest balanced window size
    int i = 0;                           // left end of window
    for (int j = 0; j < n; j++) {        // j = right end (current max)
        while ((long) nums[j] > (long) k * nums[i]) { // too spread out
            i++;                         // shrink from the left
        }
        best = Math.max(best, j - i + 1);// keep widest valid window
    }
    return n - best;                     // remove everything outside it
}

int minRemoval(vector<int>& nums, int k) {
    sort(nums.begin(), nums.end());      // min/max become window ends
    int n = nums.size();
    int best = 0;                        // largest balanced window size
    int i = 0;                           // left end of window
    for (int j = 0; j < n; j++) {        // j = right end (current max)
        while ((long long) nums[j] > (long long) k * nums[i]) { // spread
            i++;                         // shrink from the left
        }
        best = max(best, j - i + 1);     // keep widest valid window
    }
    return n - best;                     // remove everything outside it
}

Explanation

The balanced condition only involves the minimum and maximum of the kept elements. So whichever values we keep, the order does not matter — we can sort first and then think of the kept elements as a contiguous range of the sorted array.

After sorting, the smallest kept element is the left end of a window and the largest is the right end. The condition max ≤ k · min becomes nums[j] ≤ k · nums[i] for a window [i, j]. To remove the fewest elements we want to keep the most, i.e. find the widest window that satisfies this.

We use a two-pointer sliding window. As the right pointer j sweeps over the sorted array, it brings in larger maximums. Whenever nums[j] > k · nums[i] the window is too spread out, so we advance the left pointer i until the condition holds again. Each window [i, j] is the largest valid window ending at j.

We track best, the maximum window length seen. Because i only ever moves forward, every element is visited a constant number of times after the sort.

The answer is n - best: keep the best balanced window and remove everything else. For nums = [2, 1, 5], k = 2 the sorted array is [1, 2, 5]; the widest valid window is [1, 2] (length 2), so we remove 3 - 2 = 1 element.

Time: O(n log n) Space: O(1) extra (in-place sort)