Minimum Removals to Balance Array
Asked at Salesforce
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.
Asked At
| Company | Difficulty | |
|---|---|---|
| Salesforce | MEDIUM | View all Salesforce questions → |
How to Think About It
Brute force: try all subsets of elements and check if the range is ≤ k — O(2^n), not practical.
Sort the array and use two pointers to find the longest subarray where arr[right] - arr[left] ≤ k.
For each left pointer, expand right until the range exceeds k, then count elements inside.
The answer is n minus the length of the longest valid subarray found by the two-pointer technique.
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.
What Trips People Up in Real Interviews
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.
Solution Code
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_keepFrequently 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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.