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

Thinking

The remainder is balanced iff its maximum is at most \(k\) times its minimum. Deletion is equivalent to keeping a contiguous segment after sorting. Enumerating subsets fails at \(n\le 10^5\).

After sorting, if \(i\) is the left end (the minimum), the right end cannot exceed \(k\cdot \textit{nums}[i]\). Binary search finds the first index \(j\) past that bound; \([i,j)\) may be kept.

Track the longest window; the answer is \(n\) minus that length. Sorting makes the extrema of a window its two ends.

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;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn min_removal(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort();
        let mut cnt = 0;
        let n = nums.len();
        for i in 0..n {
            let mut j = n;
            let target = nums[i] as i64 * k as i64;
            if target <= nums[n - 1] as i64 {
                j = nums.partition_point(|&x| x as i64 <= target);
            }
            cnt = cnt.max(j - i);
        }
        (n - cnt) as i32
    }
}

Solution 2: Sorting + Two Pointers

Thinking

The previous method binary-searches every left end and pays an extra \(\log n\). The feasible right end is monotone in the left end, so two pointers replace the searches.

Advance \(r\) while \(\textit{nums}[r]\le \textit{nums}[l]\cdot k\). Each increment of \(l\) only moves \(r\) rightward. The answer is the minimum of \(n-(r-l)\).

Sorting remains; the scan is linear and avoids overflow handling around a binary-search bound.

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.

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
 9
10
class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        nums.sort()
        ans = n = len(nums)
        r = 0
        for l in range(n):
            while r < n and nums[r] <= nums[l] * k:
                r += 1
            ans = min(ans, n - (r - l))
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution {
    public int minRemoval(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        int ans = n;
        int r = 0;
        for (int l = 0; l < n; l++) {
            while (r < n && nums[r] <= (long) nums[l] * k) {
                r++;
            }
            ans = Math.min(ans, n - (r - l));
        }
        return ans;
    }
}

 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 n = nums.size();
        int ans = n;
        int r = 0;
        for (int l = 0; l < n; l++) {
            while (r < n && nums[r] <= (long long) nums[l] * k) {
                r++;
            }
            ans = min(ans, n - (r - l));
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
func minRemoval(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    ans := n
    r := 0
    for l := 0; l < n; l++ {
        for r < n && nums[r] <= nums[l]*k {
            r++
        }
        ans = min(ans, n-(r-l))
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
function minRemoval(nums: number[], k: number): number {
    nums.sort((a, b) => a - b);
    const n = nums.length;
    let ans = n;
    let r = 0;
    for (let l = 0; l < n; l++) {
        while (r < n && nums[r] <= nums[l] * k) {
            r++;
        }
        ans = Math.min(ans, n - (r - l));
    }
    return ans;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
impl Solution {
    pub fn min_removal(mut nums: Vec<i32>, k: i32) -> i32 {
        nums.sort();
        let n = nums.len();
        let mut ans = n;
        let mut r = 0;
        let k = k as i64;
        for l in 0..n {
            while r < n && nums[r] as i64 <= nums[l] as i64 * k {
                r += 1;
            }
            ans = ans.min(n - (r - l));
        }
        ans as i32
    }
}

Comments