LeetCode 3634 - Minimum Removals to Balance Array

Difficulty: 🟡 Medium
Topics: Array, Binary Search, Sliding Window, Sorting

Solution

Problem Understanding

The problem asks us to transform a given integer array nums into a balanced array with the minimum number of removals. An array is defined as balanced if its maximum element does not exceed k times its minimum element. Formally, for array A, it must satisfy:

$$\max(A) \le k \cdot \min(A)$$

We are allowed to remove any number of elements, but the array cannot be emptied completely. If an array has only one element, it is trivially balanced.

The input consists of an array of integers nums with length up to $10^5$ and elements up to $10^9$. The multiplier k is also bounded up to $10^5$. The output is a single integer: the minimum number of elements to remove to achieve balance.

Important observations and edge cases:

Arrays of length 1 are always balanced.
Arrays already satisfying the condition require zero removals.
Large arrays with a wide range of values require an efficient approach; naive solutions may not terminate within reasonable time.

Approaches

Brute Force: One could enumerate all non-empty subsets of nums and check whether the subset is balanced. This is guaranteed to find the minimum number of removals because it considers all possibilities. However, the number of subsets grows exponentially ($2^n$), making this infeasible for $n$ up to $10^5$.

Key Insight for Optimal Approach: Sorting nums allows us to examine only contiguous subsequences. After sorting, any balanced subarray will be contiguous because if nums[i] is the minimum and nums[j] is the maximum of a balanced subarray, all elements in between are also within the allowed range $[nums[i], k \cdot nums[i]]$. This reduces the problem to finding the longest contiguous subarray that satisfies:

$$\text{nums[j]} \le k \cdot \text{nums[i]}$$

Once we know the size of the longest balanced subarray, the minimum removals is:

$$\text{len(nums)} - \text{len(longest balanced subarray)}$$

This can be efficiently achieved using a sliding window technique.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n)	O(n)	Enumerate all non-empty subsets and check balance
Optimal	O(n log n)	O(1)	Sort and use two-pointer sliding window to find longest balanced subarray

Algorithm Walkthrough

Sort the array nums in ascending order. This ensures that for any contiguous segment [i..j], nums[i] is the minimum and nums[j] is the maximum.
Initialize two pointers, i = 0 and j = 0. Pointer i represents the start of the candidate balanced subarray, and j will expand to include as many elements as possible.
Expand j while the subarray is valid. Specifically, while nums[j] <= nums[i] * k, increment j. This ensures the maximum element in the window is at most k times the minimum element.
Track the size of the longest valid window as max_len = max(max_len, j - i).
Move i forward and repeat the process until i reaches the end of the array. Because nums is sorted, moving i forward only increases the minimum, so we maintain correctness.
Compute minimum removals as len(nums) - max_len.

Why it works: Sorting guarantees that the maximum element in any contiguous subarray is at the rightmost index. By maintaining a window that satisfies the balance condition, we ensure that any longer valid subarray is captured. Since we aim to maximize the window length, subtracting it from the total gives the minimum removals.

Python Solution

from typing import List

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        nums.sort()
        n = len(nums)
        max_len = 0
        i = 0
        
        for j in range(n):
            while nums[j] > nums[i] * k:
                i += 1
            max_len = max(max_len, j - i + 1)
        
        return n - max_len

Implementation Walkthrough: We first sort nums to guarantee contiguous subarrays represent candidate balanced arrays. We iterate j from 0 to n-1, and for each j, we move i forward until nums[j] <= nums[i] * k holds. max_len is updated to reflect the size of the longest window. Finally, n - max_len gives the minimum removals.

Go Solution

import "sort"

func minRemoval(nums []int, k int) int {
    sort.Ints(nums)
    n := len(nums)
    maxLen := 0
    i := 0

    for j := 0; j < n; j++ {
        for nums[j] > nums[i]*k {
            i++
        }
        if j-i+1 > maxLen {
            maxLen = j - i + 1
        }
    }
    
    return n - maxLen
}

Go-specific notes: Sorting uses sort.Ints. Slices are used instead of arrays, and we explicitly track the window with indices i and j. No concern about integer overflow exists within the problem constraints.

Worked Examples

Example 1: nums = [2, 1, 5], k = 2

Sort: [1, 2, 5]
Sliding window:
i=0, j=0: window [1] valid, max_len = 1
i=0, j=1: window [1,2] valid, max_len = 2
i=0, j=2: 5 > 1*2, increment i to 1 → 5 > 2*2, increment i to 2 → window [5], max_len remains 2
Minimum removals: 3 - 2 = 1

Example 2: nums = [1,6,2,9], k = 3

Sort: [1,2,6,9]
Sliding window:
i=0, j=0: [1] valid
i=0, j=1: [1,2] valid
i=0, j=2: 6 > 1*3, increment i to 1 → 6 > 2*3, increment i to 2 → [6]
i=2, j=3: 9 > 6*3 false → [6,9] valid? 9 <= 6*3 → true, window size = 2
Maximum length = 2, removals = 4 - 2 = 2

Example 3: nums = [4,6], k = 2

Sort: [4,6]
Sliding window:
i=0, j=0: [4] valid
i=0, j=1: [4,6] valid, since 6 <= 4*2
Maximum length = 2, removals = 0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates. Sliding window runs in O(n)
Space	O(1)	Sorting in-place (or O(n) if implementation creates a copy)

Sorting ensures we can evaluate contiguous segments efficiently, and the sliding window guarantees we only scan each element once.

Test Cases

# Provided examples
assert Solution().minRemoval([2,1,5], 2) == 1  # single removal required
assert Solution().minRemoval([1,6,2,9], 3) == 2  # remove extremes
assert Solution().minRemoval([4,6], 2) == 0  # already balanced

# Edge cases
assert Solution().minRemoval([1], 10) == 0  # single element
assert Solution().minRemoval([1,1,1,1], 1) == 0  # all equal
assert Solution().minRemoval([1,1000000000], 1000000000) == 0  # very large k
assert Solution().minRemoval([1,1000000000], 1) == 1  # large difference, k too small
assert Solution().minRemoval(list(range(1, 101)), 2) == 50  # larger range

Test	Why
`[2,1,5], 2`	Simple removal case
`[1,6,2,9], 3`	Requires removing multiple extremes
`[4,6], 2`	Already balanced
`[1]`	Single element, trivial case
`[1,1,1,1]`	All elements equal