MediumArrayBinary SearchSliding WindowSortingUpdated Sep 2026

3634. Minimum Removals to Balance Array

Asked at Salesforce

Difficulty

Medium

Time

O(n log n)

Space

O(1) extra (ignoring the space u

Pattern

Array

Companies

1

Problem

You get an integer array nums and an integer k. An array is called balanced when its largest element is at most k times its smallest element. In other words, max <= min * k.

You may delete any elements you like, but the array must not become empty. Return the minimum number of deletions needed to make the remaining array balanced.

A single remaining element is always balanced, because its max and min are the same value. So an answer always exists.

Keep a group, drop the rest

nums215012Keep 2 and 1 (green). Drop 5 (red) because 5 > 1 * 2.balanced: max <= min * kkeep [2,1]: 2 <= 1 * 2 ✓keep all: 5 <= 1 * 2 ✗
We want the biggest group we can keep where the largest value is at most k times the smallest value.

Constraints

  • ●1 <= nums.length <= 10^5
  • ●1 <= nums[i] <= 10^9
  • ●1 <= k <= 10^5

Examples

Example 1
Inputnums = [2,1,5], k = 2
Output1
WhyDelete 5 and keep [2,1]. Now max = 2, min = 1, and 2 <= 1 * 2, so the array is balanced. Deleting nothing fails because 5 > 1 * 2, so 1 is the smallest possible answer.
Example 2
Inputnums = [1,6,2,9], k = 3
Output2
WhyDelete 1 and 9, keeping [6,2]. Then max = 6, min = 2, and 6 <= 2 * 3. Keeping three elements never works here, so 2 deletions is optimal.
Example 3
Inputnums = [4,6], k = 2
Output0
WhyThe array is already balanced: 6 <= 4 * 2. Nothing needs to be removed.

Asked At

1 companies
CompanyDifficulty
SalesforceMediumView all Salesforce questions →

How to Think About It

1

Brute force: try all subsets of elements and check if the range is ≤ k — O(2^n), not practical.

2

Sort the array and use two pointers to find the longest subarray where arr[right] - arr[left] ≤ k.

3

For each left pointer, expand right until the range exceeds k, then count elements inside.

4

The answer is n minus the length of the longest valid subarray found by the two-pointer technique.

5

Time complexity is O(n log n) for sorting plus O(n) for the two-pointer scan.

Optimal Approach

Sort the array in ascending order. Use a sliding window with two pointers. For each starting index left, expand right as far as possible while arr[right] - arr[left] ≤ k. The length of the window (right - left + 1) is the number of elements we can keep. The answer is n minus the maximum window length. This works because after sorting, the minimum is always at left and the maximum at right within the window.

Sort, then slide a window

sorted numskeep 2125012leftrightWindow [1,2]: 2 - 1 = 1 <= k, so both elements canstay.sorted nums125012leftrightExtend right to 5: 5 - 1 = 4 > k, so move left forwarduntil the range fits again.answer = n - longest windowlongest = 2, n = 3answer = 1
After sorting, the smallest value of a window is on the left and the largest is on the right, so one comparison checks the whole window.
ComplexityTime O(n log n)Space O(1) extra (ignoring the space uSorting costs O(n log n); the two-pointer scan afterwards touches each element at most twice, which is O(n).

What Trips People Up in Real Interviews

1

Reframe the problem: minimum removals = n - longest valid subarray.

2

Clarify whether the threshold k is inclusive (max - min ≤ k) or strict (< k).

3

Mention sorting first — it reduces the 2D problem to a 1D sliding window.

4

If duplicates exist, clarify whether they count as separate elements.

5

Discuss why binary search on sorted array could also work: for each left, binary search for the farthest right.

Solution Code

O(n log n) time
def min_removals(arr, k):
    arr.sort()
    n = len(arr)
    max_keep = 0
    left = 0
    for right in range(n):
        while arr[right] - arr[left] > k:
            left += 1
        max_keep = max(max_keep, right - left + 1)
    return n - max_keep

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Minimum Removals to Balance Array problem?

Given an array of integers, find the minimum number of elements to remove so that the remaining elements form a balanced array where the difference between the maximum and minimum values is at most a given threshold k. This is equivalent to finding the longest subarray where max - min ≤ k. Sorting the array first simplifies the problem significantly.

How do you solve Minimum Removals to Balance Array?

The optimal approach runs in O(n log n) time and O(1) extra (ignoring the space u space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Minimum Removals to Balance Array?

Minimum Removals to Balance Array is asked at Salesforce. It is a medium difficulty problem.

What are common mistakes on Minimum Removals to Balance Array?
  • Reframe the problem: minimum removals = n - longest valid subarray.
  • Clarify whether the threshold k is inclusive (max - min ≤ k) or strict (< k).
  • Mention sorting first — it reduces the 2D problem to a 1D sliding window.
  • If duplicates exist, clarify whether they count as separate elements.
  • Discuss why binary search on sorted array could also work: for each left, binary search for the farthest right.