Skip to content

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 get nums = [2, 1].
  • Now 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:

  • Remove nums[0] = 1 and nums[3] = 9 to get nums = [6, 2].
  • Now 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:

  • Since nums is already balanced as 6 <= 4 * 2, no elements need to be removed.

 

Constraints:

  • 1 <= nums.length <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 105

Solutions

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}\).

1
2
3
4
5
6
7
8
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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;
}

Comments