Description
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
Solutions
This code uses a sliding window algorithm to find the minimum number of elements to remove from an array so the remaining elements satisfy a constraint: each element must be at most k times the smallest element in the window. It first sorts the array to make comparisons meaningful, then uses two pointers (left and right) to maintain a valid window. As right advances, if nums[right] is within k times nums[left], the window is valid and the code tracks the maximum window size; otherwise, it shrinks the window by moving left forward. Finally, it returns the total length minus the largest valid window size—the minimum number of removals needed.
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var minRemoval = function(nums, k) {
nums.sort((a, b) => a - b);
let left = 0;
let right = 0;
let res = 0;
while (right < nums.length) {
if (nums[right] <= nums[left] * k) {
res = Math.max(res, right - left + 1);
right++;
} else {
left++;
}
}
return nums.length - res;
};