Welcome to Subscribe On Youtube
3634. Minimum Removals to Balance Array
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] = 5
to getnums = [2, 1]
. - Now
max = 2
,min = 1
andmax <= min * k
as2 <= 1 * 2
. Thus, the answer is 1.
Example 2:
Input: nums = [1,6,2,9], k = 3
Output: 2
Explanation:
- Remove
nums[0] = 1
andnums[3] = 9
to getnums = [6, 2]
. - Now
max = 6
,min = 2
andmax <= min * k
as6 <= 2 * 3
. Thus, the answer is 2.
Example 3:
Input: nums = [4,6], k = 2
Output: 0
Explanation:
- Since
nums
is already balanced as6 <= 4 * 2
, no elements need to be removed.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
1 <= k <= 105
Solutions
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}$.
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 $\textit{nums}$.
-
class Solution { public int minRemoval(int[] nums, int k) { Arrays.sort(nums); int cnt = 0; int n = nums.length; for (int i = 0; i < n; ++i) { int j = n; if (1L * nums[i] * k <= nums[n - 1]) { j = Arrays.binarySearch(nums, nums[i] * k + 1); j = j < 0 ? -j - 1 : j; } cnt = Math.max(cnt, j - i); } return n - cnt; } }
-
class Solution { public: int minRemoval(vector<int>& nums, int k) { ranges::sort(nums); int cnt = 0; int n = nums.size(); for (int i = 0; i < n; ++i) { int j = n; if (1LL * nums[i] * k <= nums[n - 1]) { j = upper_bound(nums.begin(), nums.end(), 1LL * nums[i] * k) - nums.begin(); } cnt = max(cnt, j - i); } return n - 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) - cnt
-
func minRemoval(nums []int, k int) int { sort.Ints(nums) n := len(nums) cnt := 0 for i := 0; i < n; i++ { j := n if int64(nums[i])*int64(k) <= int64(nums[n-1]) { target := int64(nums[i])*int64(k) + 1 j = sort.Search(n, func(x int) bool { return int64(nums[x]) >= target }) } cnt = max(cnt, j-i) } return n - cnt }
-
function minRemoval(nums: number[], k: number): number { nums.sort((a, b) => a - b); const n = nums.length; let cnt = 0; for (let i = 0; i < n; ++i) { let j = n; if (nums[i] * k <= nums[n - 1]) { const target = nums[i] * k + 1; j = _.sortedIndexBy(nums, target, x => x); } cnt = Math.max(cnt, j - i); } return n - cnt; }