LeetCode Problem Workspace
Minimum Removals to Balance Array
Determine the fewest elements to remove from nums so the remaining array satisfies the maximum-to-minimum ratio within k times.
0
Topics
6
Code langs
0
Related
Practice Focus
Medium · Minimum Removals to Balance Array core interview pattern
Answer-first summary
Determine the fewest elements to remove from nums so the remaining array satisfies the maximum-to-minimum ratio within k times.
Ace coding interviews with Interview AiBoxInterview AiBox guidance for Minimum Removals to Balance Array core interview pattern
This problem requires finding the minimum number of elements to remove so the array becomes balanced, meaning the maximum value does not exceed k times the minimum value. Sorting the array and using a sliding window helps efficiently identify the largest balanced subarray. The final answer is the difference between the total array length and the longest valid subarray length.
Problem Statement
You are given an integer array nums and an integer k. An array is considered balanced if the largest element is at most k times the smallest element. You may remove any number of elements but cannot make the array empty.
Determine the minimum number of elements to remove from nums to make it balanced. Return the minimum removals required, ensuring the remaining subarray satisfies the ratio constraint.
Examples
Example 1
Input: nums = [2,1,5], k = 2
Output: 1
Example 2
Input: nums = [1,6,2,9], k = 3
Output: 2
Example 3
Input: nums = [4,6], k = 2
Output: 0
Constraints
- 1 <= nums.length <= 105
- 1 <= nums[i] <= 109
- 1 <= k <= 105
Solution Approach
Sort the Array
Begin by sorting nums in ascending order. Sorting ensures that any subarray you consider will have the minimum at the start and maximum at the end, which simplifies checking the k-times condition efficiently.
Sliding Window Technique
Use two pointers i and j to define a window. Expand j while nums[j] <= k * nums[i]. When the condition fails, move i forward. Track the maximum window length, which corresponds to the largest balanced subarray.
Compute Minimum Removals
After identifying the largest window where the array is balanced, subtract its length from the total length of nums. This difference gives the minimum number of elements that must be removed to satisfy the balanced array condition.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Sorting takes O(n log n) time. The two-pointer window scans the array once, giving O(n) time after sorting. Space is O(1) if sorting is in-place, otherwise O(n) for the sorted copy.
What Interviewers Usually Probe
- Sorting is likely expected to simplify the ratio check.
- Sliding window hints at using two pointers to maximize the valid subarray length.
- They may probe edge cases like duplicates or large k values to check correctness.
Common Pitfalls or Variants
Common pitfalls
- Forgetting that removing elements cannot leave the array empty.
- Incorrectly checking the k-times condition without sorting first.
- Using nested loops leading to O(n^2) instead of two-pointer linear scan after sorting.
Follow-up variants
- Find the minimum removals when the array must remain contiguous after removal.
- Balance the array using only even-indexed elements with the k-times condition.
- Compute the minimum removals when elements can be doubled or halved instead of removed.
FAQ
What does 'balanced' mean in Minimum Removals to Balance Array?
Balanced means the maximum element in the remaining array is at most k times the minimum element.
Can the array be empty after removals?
No, at least one element must remain in the array after removals.
Is sorting necessary to solve this problem efficiently?
Yes, sorting allows the two-pointer window approach to check the k-times condition in linear time after sorting.
What is the core pattern for this problem?
The core pattern is minimum removals to achieve a subarray satisfying a max-to-min ratio using a sliding window.
What is the expected time complexity?
Time complexity is O(n log n) due to sorting, followed by O(n) for the two-pointer scan.
Solution
Solution 1: Sorting + Binary Search
We first sort the array, then enumerate each element $\textit{nums}[i]$ from small to large as the minimum value of the balanced array. The maximum value $\textit{max}$ of the balanced array must satisfy $\textit{max} \leq \textit{nums}[i] \times k$. Therefore, we can use binary search to find the index $j$ of the first element greater than $\textit{nums}[i] \times k$. At this point, the length of the balanced array is $j - i$. We record the maximum length $\textit{cnt}$, and the final answer is the array length minus $\textit{cnt}$.
class Solution:
def minRemoval(self, nums: List[int], k: int) -> int:
nums.sort()
cnt = 0
for i, x in enumerate(nums):
j = bisect_right(nums, k * x)
cnt = max(cnt, j - i)
return len(nums) - cntSolution 2: Sorting + Two Pointers
We first sort the array, then use two pointers to maintain a sliding window. The left pointer $l$ enumerates each element $\textit{nums}[l]$ from left to right as the minimum value of the balanced array. The right pointer $r$ keeps moving right until $\textit{nums}[r]$ is greater than $\textit{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.
class Solution:
def minRemoval(self, nums: List[int], k: int) -> int:
nums.sort()
cnt = 0
for i, x in enumerate(nums):
j = bisect_right(nums, k * x)
cnt = max(cnt, j - i)
return len(nums) - cnt