3634. Minimum Removals to Balance Array

Intuition

After sorting, we need the longest contiguous subarray where max <= min * k. Since array is sorted, max is the rightmost element and min is the leftmost. Use two pointers to find the longest valid window.

Solution

1. Sort the array: After sorting, any contiguous subarray has min at left and max at right.

2. Two pointer / sliding window:

   • Expand right pointer to include more elements
   • If nums[r] > nums[l] * k, shrink from left until valid

3. Track maximum length: The longest valid window gives the maximum elements we can keep.

4. Return removals: n - maxLen = minimum elements to remove.

Why Contiguous After Sort?

After sorting, keeping a contiguous subarray is optimal because:

• Removing middle elements doesn't help (doesn't change min/max of remaining)
• We want elements as close in value as possible
• Contiguous subarray in sorted order minimizes the max/min ratio

Complexity

• Time: O(n log n), sorting dominates, two-pointer scan is O(n)
• Space: O(1), ignoring sort space, only constant extra variables

Edge Cases

• Single element → return 0 (always balanced)
• All elements equal → return 0
• All elements already satisfy condition → return 0
• Large values → use long in Java to prevent overflow on nums[l] * k

from typing import List


class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        """
        3634. Minimum Removals to Balance Array
        Time: O(n log n)
        Space: O(1)
        """
        nums.sort()
        n = len(nums)
        
        l = 0
        max_len = 1
        
        for r in range(n):
            while nums[r] > nums[l] * k:
                l += 1
            max_len = max(max_len, r - l + 1)
        
        return n - max_len

import java.util.Arrays;

/**
 * 3634. Minimum Removals to Balance Array
 * Time: O(n log n)
 * Space: O(1)
 */
class Solution {
    public int minRemoval(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        
        int l = 0;
        int maxLen = 1;
        
        for (int r = 0; r < n; r++) {
            while ((long) nums[r] > (long) nums[l] * k) {
                l++;
            }
            maxLen = Math.max(maxLen, r - l + 1);
        }
        
        return n - maxLen;
    }
}