Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Minimizing removals is equivalent to retaining as many elements as possible with maximum <= k * minimum. After sorting, any values between an eligible minimum and maximum can also be retained, so an optimal retained set is a contiguous sorted window.

Approach

Sort the array. Move a right pointer forward, and while its value exceeds k times the left value, advance the left pointer. Record the largest valid window length after each adjustment. Return the original length minus that maximum.

For a fixed right endpoint, removing smaller left values is the only way to repair the inequality. Once a left endpoint fails, it cannot become valid again for any larger right value, so the left pointer never needs to move backward. The positive-value and k >= 1 constraints guarantee that every singleton is valid, ensuring a nonempty retained array.

class Solution:
    def minRemoval(self, nums: List[int], k: int) -> int:
        n = len(nums)
        nums.sort()
        mx = 0
        l = 0

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

        return n - mx

Complexity analysis

Let n = nums.length. Time: O(n log n). Auxiliary space: O(n) in the worst case for sorting.