Is Minimum Removals to Balance Array easy or hard?

Minimum Removals to Balance Array is typically classified as a medium difficulty problem. The key insight is recognizing that sorting transforms the constraint into a contiguous window problem solvable with two pointers.

Minimum Removals to Balance Array Python/Java solution

Most implementations first sort the array and then apply a two-pointer window. Python, Java, C++, and Go solutions all follow the same pattern: sort the array, expand the right pointer while the balance condition holds, and compute n minus the maximum window size.

How to solve Minimum Removals to Balance Array in O(n)?

A strict O(n) solution is not possible because the array must first be sorted to efficiently compare minimum and maximum values within candidate segments. After sorting, a sliding window finds the largest balanced subarray in O(n), resulting in O(n log n) total time.

What is the best approach for Minimum Removals to Balance Array?

The most efficient approach sorts the array and then uses a two-pointer sliding window. After sorting, expand the right pointer while nums[right] ≤ 2 × nums[left]. Track the longest valid window and subtract its size from n to get the minimum removals. This runs in O(n log n) time due to sorting and O(1) extra space.

Is Minimum Removals to Balance Array asked at Google/Amazon/Meta?

Problems involving window constraints like max ≤ 2 × min commonly appear in interviews at companies such as Amazon, Google, and Meta. They test familiarity with sorting combined with sliding window or binary search techniques.

What data structure is used in Minimum Removals to Balance Array?

The solution primarily uses arrays with sorting and a sliding window technique. Binary search can also be applied on the sorted array to locate the farthest valid element for each starting index.

What is the time complexity of Minimum Removals to Balance Array?

The optimal solution runs in O(n log n) time. Sorting the array costs O(n log n), and the two-pointer scan runs in O(n). Space complexity is O(1) if sorting is done in place.

Description Hints 2 Solution Video 23:31

3634. Minimum Removals to Balance Array

Medium47.9% acceptance4 companies

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.

Example 1:

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

Output: 1

Explanation:

Remove nums[2] = 5 to get nums = [2, 1].
Now max = 2, min = 1 and max <= min * k as 2 <= 1 * 2. Thus, the answer is 1.

Example 2:

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

Output: 2

Explanation:

Remove nums[0] = 1 and nums[3] = 9 to get nums = [6, 2].
Now max = 6, min = 2 and max <= min * k as 6 <= 2 * 3. Thus, the answer is 2.

Example 3:

Input: nums = [4,6], k = 2

Output: 0

Explanation:

Since nums is already balanced as 6 <= 4 * 2, no elements need to be removed.

Constraints:

1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹
1 <= k <= 10⁵

Asked at 4 companies

Salesforce Amazon Meta

Google

Topics

Hints open one at a time

Hint 1

Sort nums and use two pointers i and j so that the window's minimum is nums[i] and maximum is nums[j].

Hint 2

Expand j while nums[j] <= k * nums[i] to maximize the balanced window; answer = n - (j - i + 1).

23:31

Still stuck?Read 2 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def minRemoval(self, nums: List[int], k: int) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2Case 3

Input

[2,1,5]
2

Input

[1,6,2,9]
3

Input

[4,6]
2

Your code is saved on this device.Solution