Watch 10 video solutions for Minimum Removals to Balance Array, a medium level problem involving Array, Binary Search, Sliding Window. This walkthrough by codestorywithMIK has 9,363 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
| 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. |