Skip to main content
Talentd

Minimum Removals to Balance Array - Solution & Explanation

MediumArrayBinary SearchSliding WindowSorting13 min readAsked at: Amazon, Meta, Salesforce +1
Practice this problem

Problem Statement

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 <= 105
  • 1 <= nums[i] <= 109
  • 1 <= k <= 105

Approach Overview

Problem Overview: You are given an integer array and can remove any elements. The goal is to make the remaining array balanced, meaning the maximum value is at most twice the minimum value (max ā‰¤ 2 Ɨ min). Return the minimum number of removals required. The challenge is identifying the largest subset that already satisfies this constraint.

Approach 1: Sorting + Binary Search (O(n log n) time, O(1) space)

Start by sorting the array so the minimum and maximum values in any subarray are easy to compare. For each index i, treat nums[i] as the minimum of a potential balanced segment. Use binary search to find the farthest index j where nums[j] ā‰¤ 2 Ɨ nums[i]. The window [i, j] is valid because the array is sorted and every element inside satisfies the constraint. Track the maximum window length across all starting indices, then compute removals as n - maxWindow. Sorting costs O(n log n), and each binary search adds another log n, giving O(n log n) overall. This approach clearly demonstrates how ordering simplifies constraint checking.

Approach 2: Sorting + Two Pointers (O(n log n) time, O(1) space)

After sorting, use a sliding window with two pointers. The left pointer represents the minimum element and the right pointer expands the window while the condition nums[right] ā‰¤ 2 Ɨ nums[left] holds. When the condition breaks, move the left pointer forward until the window becomes valid again. This works because increasing the left pointer increases the minimum value, which may restore the balance condition. Track the largest valid window size during the scan. The two-pointer scan itself runs in O(n), so the total complexity is dominated by sorting at O(n log n). This pattern is a classic combination of sorting and sliding window techniques.

Recommended for interviews: The Sorting + Two Pointers approach is what most interviewers expect. It shows you recognize that sorting converts a global constraint into a local window condition and that you can optimize repeated searches using a sliding window instead of binary search. The binary search method still demonstrates solid understanding of ordered arrays and binary search, but the two-pointer solution is cleaner and slightly more efficient in practice.

Approach 1: Sorting + Binary Search

We first sort the array, then enumerate each element nums[i] from small to large as the minimum value of the balanced array. The maximum value max of the balanced array must satisfy max leq nums[i] times k. Therefore, we can use binary search to find the index j of the first element greater than nums[i] times k. At this point, the length of the balanced array is j - i. We record the maximum length cnt, and the final answer is the array length minus cnt.

The time complexity is O(n times log n), and the space complexity is O(log n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Approach 2: Sorting + Two Pointers

We first sort the array, then use two pointers to maintain a sliding window. The left pointer l enumerates each element nums[l] from left to right as the minimum value of the balanced array. The right pointer r keeps moving right until nums[r] is greater than nums[l] times k. At this point, the length of the balanced array is r - l, and the number of elements to be removed is n - (r - l). We record the minimum number of removals as the answer.

The time complexity is O(n times log n) and the space complexity is O(log n), where n is the length of the array nums.

Code

PythonJavaC++GoTypeScriptRust

Python

Java

C++

Go

TypeScript

Rust

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Sorting + Binary Searchā€”
Sorting + Two Pointersā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting + Binary SearchO(n log n)O(1)Good when you want a straightforward implementation using ordered lookups for each starting index.
Sorting + Two PointersO(n log n)O(1)Preferred approach after sorting when scanning for the largest valid window efficiently.

Video Solution

Minimum Removals to Balance Array | Simple Clean Intuition | Leetcode 3634 | codestorywithMIK ā€¢ codestorywithMIK ā€¢ 10,309 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Minimum Removals to Balance Array with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays