3634. Minimum Removals to Balance Array

Medium

Problem 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.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

Intuition

To make the array balanced, the difference between the largest and smallest element must not be too big: the maximum element should be at most k times the minimum. Rather than checking all possible subsets, it's easier to look for the largest possible balanced subarray since removing fewer elements is better.

If we sort the array, then for each possible starting number (minimum), the numbers that can stay must not be bigger than k times this minimum. So, we can try every possible minimum: for each one, see how many numbers (in sorted order) we can keep without breaking the balanced rule. The minimum elements to remove is the total minus the size of the biggest such group.

Binary search helps quickly find where the valid range ends for each minimum, since the array is sorted.

Solution Approach

First, sort the array nums. Sorting helps because a balanced array needs the maximum and minimum values to be within a factor of k, and this relationship is easier to check when the numbers are in order.

For each index i, think of nums[i] as the minimum value for a possible balanced subarray. To keep the subarray balanced, the largest value we include must be at most k * nums[i]. With the array sorted, we can use binary search (with bisect_right) to quickly find the rightmost index j where nums[j - 1] <= k * nums[i]. This gives the largest possible balanced sequence starting from nums[i].

Record the length of this range (j - i), and keep track of the maximum such length over all choices of the starting point. The answer is then the total array size (len(nums)) minus this maximum length, since these are the fewest elements we need to remove to achieve balance.

Key steps:

Sort nums.
For each possible starting index, use binary search to find how many elements can be kept to stay balanced.
The minimum elements to remove is len(nums) - max_balanced_length.

This approach uses sorting (O(n log n)) and binary search for each possible start (O(n log n)), making it efficient for large arrays.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Consider nums = [1, 3, 7, 15] and k = 3.

Step 1: Sort the array

Sorted nums: [1, 3, 7, 15]

Step 2: For each index, try to build the biggest balanced group that starts there

Start at index 0 (nums[0] = 1):
- The maximum allowed: 1 * 3 = 3
- Include elements ≤ 3: [1, 3] (indices 0–1)
- Next, 7 > 3 (stop here)
- Length of this group: 2 (indices 0 and 1)
Start at index 1 (nums[1] = 3):
- Maximum allowed: 3 * 3 = 9
- Include elements ≤ 9: [3, 7] (indices 1–2, also 15 > 9 so stop here)
- Length: 2 (indices 1 and 2)
Start at index 2 (nums[2] = 7):
- Maximum allowed: 7 * 3 = 21
- Include elements ≤ 21: [7, 15] (indices 2–3)
- Length: 2 (indices 2 and 3)
Start at index 3 (nums[3] = 15):
- Maximum allowed: 15 * 3 = 45
- Include [15] (only index 3)
- Length: 1

Step 3: Find the maximum group length

Maximum group length is 2.

Step 4: Compute the minimum removals

Array length = 4
Minimum elements to remove = 4 - 2 = 2.

Result: Remove two elements (for example, [7, 15] or [1, 7]) to get a balanced array.

This process shows how sorting and binary search can help find the answer efficiently for any input.

Solution Implementation

1from typing import List
2from bisect import bisect_right
3
4class Solution:
5    def minRemoval(self, nums: List[int], k: int) -> int:
6        # Sort the input list to make comparisons easier
7        nums.sort()
8        max_count = 0  # To track the size of the largest valid subarray
9
10        # Iterate through each number in the sorted list
11        for i, x in enumerate(nums):
12            # Find the insertion point for k * x in nums to get upper bound
13            # All numbers from index i to j-1 are within k times current x
14            j = bisect_right(nums, k * x)
15            max_count = max(max_count, j - i)
16
17        # The minimum removals is total numbers minus largest valid subarray
18        return len(nums) - max_count
19

1class Solution {
2    public int minRemoval(int[] nums, int k) {
3        // Sort the array to make it easier to evaluate subarrays
4        Arrays.sort(nums);
5        int maxLength = 0;
6        int n = nums.length;
7
8        // Iterate through each possible starting point
9        for (int start = 0; start < n; ++start) {
10            int end = n;
11
12            // Check if nums[start] * k is less than or equal to the maximum element
13            if (1L * nums[start] * k <= nums[n - 1]) {
14                // Find the first index where element > nums[start] * k using binary search
15                end = Arrays.binarySearch(nums, nums[start] * k + 1);
16                // If not found, adjust 'end' to the correct insertion point
17                end = end < 0 ? -end - 1 : end;
18            }
19
20            // Update the length of the largest valid subarray
21            maxLength = Math.max(maxLength, end - start);
22        }
23
24        // Return the minimum number of elements to remove
25        return n - maxLength;
26    }
27}
28

1#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6    // Finds the minimum number of elements to remove so that for every remaining pair (i, j),
7    // nums[j] <= nums[i] * k holds (with i < j).
8    int minRemoval(std::vector<int>& nums, int k) {
9        // Sort the array to allow efficient range counting.
10        std::sort(nums.begin(), nums.end());
11        int maxSubarray = 0;
12        int n = nums.size();
13
14        // Iterate over the array, treating nums[i] as potential subarray start.
15        for (int i = 0; i < n; ++i) {
16            int validEnd = n;
17
18            // Check if elements beyond i can fulfill nums[j] <= nums[i] * k.
19            if (1LL * nums[i] * k <= nums[n - 1]) {
20                // Find the first element greater than nums[i] * k using upper_bound.
21                validEnd = std::upper_bound(
22                    nums.begin(), nums.end(), 1LL * nums[i] * k
23                ) - nums.begin();
24            }
25            // Update the largest valid subarray length found so far.
26            maxSubarray = std::max(maxSubarray, validEnd - i);
27        }
28
29        // Minimum removals needed = total - maximum valid subarray size.
30        return n - maxSubarray;
31    }
32};
33

1/**
2 * Finds the minimum number of elements to remove from the array 'nums'
3 * so that for any remaining subarray, the maximum element is at most k times the minimum element.
4 *
5 * @param nums - Array of numbers
6 * @param k - The multiplier constraint
7 * @returns The minimum number of removals required
8 */
9function minRemoval(nums: number[], k: number): number {
10    // Sort the array in non-decreasing order
11    nums.sort((a, b) => a - b);
12    const n: number = nums.length;
13    let maxLength: number = 0; // Maximum length of valid subarray found
14
15    // Helper function: Binary search to find the first index where value >= target
16    function binarySearchFirstGE(arr: number[], target: number): number {
17        let left = 0, right = arr.length;
18        while (left < right) {
19            const mid = left + Math.floor((right - left) / 2);
20            if (arr[mid] < target) {
21                left = mid + 1;
22            } else {
23                right = mid;
24            }
25        }
26        return left;
27    }
28
29    // Iterate over all possible starting points
30    for (let i = 0; i < n; ++i) {
31        let endIdx = n; // Default to end of array
32
33        // If current minimum * k is still <= max element, find valid boundary
34        if (nums[i] * k <= nums[n - 1]) {
35            // Find index of the smallest number >= nums[i] * k + 1
36            const target = nums[i] * k + 1;
37            endIdx = binarySearchFirstGE(nums, target);
38        }
39        // Update maximum length of any valid subarray found
40        maxLength = Math.max(maxLength, endIdx - i);
41    }
42
43    // The answer is the number of elements outside the longest valid subarray
44    return n - maxLength;
45}
46

Time and Space Complexity

The time complexity of the code is O(n \log n), where n is the length of nums. This comes from sorting the array (O(n \log n)) and then iterating through each element and performing a binary search (bisect_right, which is O(\log n)) for each position, leading to a total of O(n \log n).

The space complexity is O(\log n), which is due to the space used by the sorting algorithm (Timsort), which requires O(\log n) auxiliary space. The rest of the algorithm uses only a constant amount of additional space.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan: