Problem Statement in English

You’re given a 0-indexed integer array nums and an integer k. In one operation, you can remove any element from nums. An array is considered balanced if the maximum elemtent in the array is at most k times larger than the minimum element in the array.

Return the minimum number of removals required to make nums balanced.

An array of size 1 is considered balanced.

Approach

All we really need to find is the longest subarray which is balanced.

The answer will be the total number of elements minus the size of this subarray.

We can achieve this using a sliding window. The window will simply store the current subarray we are considering. We will expand the right pointer of the window and whenever the condition of being balanced is violated, we will move the left pointer to the right until the condition is satisfied again.

And we’re done!

Solution in Python


class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        N = len(nums)

        nums.sort()

        l = best = 0

        for r in range(N):
            while nums[l] * k < nums[r]:
                best = max(best, r - l)
                l += 1

        best = max(best, N - l)

        return N - best

Complexity

  • Time: $O(n \log n)$
    Since we sort the array.

  • Space: $O(1)$
    Since we use only constant space.

And we are done.