Balancing an Array with Minimum Removals

Problem recap

You’re given an integer array nums and an integer k.

A (non-empty) array is balanced if: $\max(\text{array}) \le k \cdot \min(\text{array})$ max(array)≤k⋅min(array)

You may remove any number of elements (but you cannot remove all of them). Return the minimum removals needed so the remaining array becomes balanced. Arrays of size 1 are always balanced.

Constraints (important for complexity + overflow choices):

1 <= nums.length <= 1e5
1 <= nums[i] <= 1e9
1 <= k <= 1e5

Key insight: “Minimum removals” = “Keep the largest valid group”

If we keep m elements and remove the rest, removals = n - m.
So the goal becomes:

Find the maximum size of a subset whose max ≤ k × min, then answer = n - maxSize.

Now here’s the trick that makes this problem easy after sorting:

After sorting, the best subset is a contiguous window

Sort nums in non-decreasing order.

If we pick a minimum value nums[l] and a maximum value nums[r] that satisfy: $nums[r] \le k \cdot nums[l]$ nums[r]≤k⋅nums[l]

then every value between them (indices l..r) is also between min and max, so adding them cannot break the condition.

✅ That means an optimal solution is simply:

Find the longest subarray window in the sorted array where nums[right] <= k * nums[left].

Optimal approach: Sort + Sliding Window (Two Pointers)

Plan

Sort the array.
Use two pointers l and r:
- l is the current minimum.
- Move r as far right as possible while nums[r] <= k * nums[l].
Track the maximum window length best = max(best, r - l).
Answer = n - best.

Why this is fast

Sorting: O(n log n)
Sliding window: O(n) because r only moves forward

Total: O(n log n) time, O(1)/O(log n) extra space (depending on sorting implementation).

Walkthrough example

Example: nums = [1,6,2,9], k = 3
Sort → [1,2,6,9]

l=0 (min=1): allowed max = 3 → window [1,2] length 2
l=1 (min=2): allowed max = 6 → window [2,6] length 2
l=2 (min=6): allowed max = 18 → window [6,9] length 2

Best kept = 2 → removals = 4 – 2 = 2 ✅

Correctness sketch (why the sliding window works)

Sorting fixes the minimum at the left edge of the window.
For a fixed l, any valid solution with minimum nums[l] can include all values up to the largest r that still satisfies nums[r] <= k*nums[l].
Therefore, for each l, the best you can do is the widest such r.
Taking the best over all l gives the global maximum kept elements → minimum removals.

Common pitfalls

1) Overflow in `k * nums[l]`

Even though inputs fit in 32-bit, k * nums[l] can be as large as: $10^5 \times 10^9 = 10^{14}$ 105×109=1014

So you must compute it in 64-bit (long long in C++, long in Java, normal int is fine in Python).

2) Don’t reset `r` for each `l`

This is what makes it O(n) after sorting. r only moves forward.

Python solution (recommended)

from typing import List

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)

        best = 1  # at least one element is always balanced
        r = 0

        for l in range(n):
            if r < l:
                r = l

            limit = nums[l] * k  # Python int won't overflow
            while r < n and nums[r] <= limit:
                r += 1

            best = max(best, r - l)

        return n - best

C++ solution

class Solution {
public:
    int minRemoval(vector<int>& nums, int k) {
        sort(nums.begin(), nums.end());
        int n = (int)nums.size();

        int best = 1;
        int r = 0;

        for (int l = 0; l < n; l++) {
            if (r < l) r = l;

            long long limit = 1LL * nums[l] * k;
            while (r < n && (long long)nums[r] <= limit) {
                r++;
            }
            best = max(best, r - l);
        }

        return n - best;
    }
};

Java solution

import java.util.Arrays;

class Solution {
    public int minRemoval(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;

        int best = 1;
        int r = 0;

        for (int l = 0; l < n; l++) {
            if (r < l) r = l;

            long limit = 1L * nums[l] * k;
            while (r < n && (long) nums[r] <= limit) {
                r++;
            }
            best = Math.max(best, r - l);
        }

        return n - best;
    }
}

Optional alternative: Sort + Binary Search

You can also sort and, for each i, binary search the first index > k*nums[i] to get the window size. That’s simpler conceptually for some people, but it’s O(n log n) after sorting instead of O(n).