Skip to content

3958. Minimum Removals To Balance Array

3958. Minimum Removals to Balance Array

Medium

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

Solution

class Solution {
    public int minRemoval(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        if (n == 1) return 0;
        int low = 0, high = (int)(n), ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (ok(mid, nums, k)) {
                ans = mid;
                high = mid - 1;
            }
            else low = mid + 1;
        }
        return ans;
    }
    private boolean ok(int target, int arr[], int k) {
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            int totalDel = i;
            long req = k * 1L * arr[i];

            int get = findGreater(arr, i + 1, n - 1, req);
            if (get != -1) totalDel += n - get;
            if (totalDel <= target) return true;
        }
        return false;
    }
    private int findGreater(int arr[], int low, int high, long req) {
        int n = arr.length;
        int ans = -1;
        while (low <= high) {
            int mid = low + (high - low) / 2;
            if (arr[mid] > req) {
                ans = mid;
                high = mid - 1;
            }
            else low = mid + 1;
        }
        return ans;
    }
}

Complexity Analysis

  • Time Complexity: O(?)
  • Space Complexity: O(?)

Explanation

[Add detailed explanation here]