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, and the condition always holds true.
Example 1:
Input: nums = [2,1,5], k = 2
Output: 1
Explanation:
nums[2] = 5 to get nums = [2, 1].max = 2, min = 1 and max <= min * k as 2 <= 1 * 2. Thus, the answer is 1.Example 2:
Input: nums = [1,6,2,9], k = 3
Output: 2
Explanation:
nums[0] = 1 and nums[3] = 9 to get nums = [6, 2].max = 6, min = 2 and max <= min * k as 6 <= 2 * 3. Thus, the answer is 2.Example 3:
Input: nums = [4,6], k = 2
Output: 0
Explanation:
nums is already balanced as 6 <= 4 * 2, no elements need to be removed.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 105Problem Overview: You are given an integer array and can remove any elements. The goal is to make the remaining array balanced, meaning the maximum value is at most twice the minimum value (max ≤ 2 × min). Return the minimum number of removals required. The challenge is identifying the largest subset that already satisfies this constraint.
Approach 1: Sorting + Binary Search (O(n log n) time, O(1) space)
Start by sorting the array so the minimum and maximum values in any subarray are easy to compare. For each index i, treat nums[i] as the minimum of a potential balanced segment. Use binary search to find the farthest index j where nums[j] ≤ 2 × nums[i]. The window [i, j] is valid because the array is sorted and every element inside satisfies the constraint. Track the maximum window length across all starting indices, then compute removals as n - maxWindow. Sorting costs O(n log n), and each binary search adds another log n, giving O(n log n) overall. This approach clearly demonstrates how ordering simplifies constraint checking.
Approach 2: Sorting + Two Pointers (O(n log n) time, O(1) space)
After sorting, use a sliding window with two pointers. The left pointer represents the minimum element and the right pointer expands the window while the condition nums[right] ≤ 2 × nums[left] holds. When the condition breaks, move the left pointer forward until the window becomes valid again. This works because increasing the left pointer increases the minimum value, which may restore the balance condition. Track the largest valid window size during the scan. The two-pointer scan itself runs in O(n), so the total complexity is dominated by sorting at O(n log n). This pattern is a classic combination of sorting and sliding window techniques.
Recommended for interviews: The Sorting + Two Pointers approach is what most interviewers expect. It shows you recognize that sorting converts a global constraint into a local window condition and that you can optimize repeated searches using a sliding window instead of binary search. The binary search method still demonstrates solid understanding of ordered arrays and binary search, but the two-pointer solution is cleaner and slightly more efficient in practice.
We first sort the array, then enumerate each element nums[i] from small to large as the minimum value of the balanced array. The maximum value max of the balanced array must satisfy max leq nums[i] times k. Therefore, we can use binary search to find the index j of the first element greater than nums[i] times k. At this point, the length of the balanced array is j - i. We record the maximum length cnt, and the final answer is the array length minus cnt.
The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array nums.
We first sort the array, then use two pointers to maintain a sliding window. The left pointer l enumerates each element nums[l] from left to right as the minimum value of the balanced array. The right pointer r keeps moving right until nums[r] is greater than nums[l] times k. At this point, the length of the balanced array is r - l, and the number of elements to be removed is n - (r - l). We record the minimum number of removals as the answer.
The time complexity is O(n times log n) and the space complexity is O(log n), where n is the length of the array nums.
| Approach | Complexity |
|---|---|
| Sorting + Binary Search | — |
| Sorting + Two Pointers | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Binary Search | O(n log n) | O(1) | Good when you want a straightforward implementation using ordered lookups for each starting index. |
| Sorting + Two Pointers | O(n log n) | O(1) | Preferred approach after sorting when scanning for the largest valid window efficiently. |
Minimum Removals to Balance Array | Simple Clean Intuition | Leetcode 3634 | codestorywithMIK • codestorywithMIK • 9,363 views views
Watch 9 more video solutions →Practice Minimum Removals to Balance Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor