Minimum Removals to Balance Array - Video Solutions
Minimum Removals to Balance Array | Simple Clean Intuition | Leetcode 3634 | codestorywithMIK
Minimum Removals to Balance Array - Video Solution
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 10,309 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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:
- Remove
nums[2] = 5to getnums = [2, 1]. - Now
max = 2,min = 1andmax <= min * kas2 <= 1 * 2. Thus, the answer is 1.
Example 2:
Input: nums = [1,6,2,9], k = 3
Output: 2
Explanation:
- Remove
nums[0] = 1andnums[3] = 9to getnums = [6, 2]. - Now
max = 6,min = 2andmax <= min * kas6 <= 2 * 3. Thus, the answer is 2.
Example 3:
Input: nums = [4,6], k = 2
Output: 0
Explanation:
- Since
numsis already balanced as6 <= 4 * 2, no elements need to be removed.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= k <= 105
Approach Overview
Problem 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.
Complexity Analysis
| 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. |