Minimum Removals to Balance Array solution and explanation
Google
9 more videos on this problem
Minimum Removals to Balance Array | Simple Clean Intuition | Leetcode 3634 | codestorywithMIKcodestorywithMIK · 23:31 · 10K views
3634. Minimum Removals to Balance Array | Leetcode Daily - PythonLeetcode Daily · 8:30 · 1K views
Minimum Removals to Balance Array | LeetCode 3634 | Complete Intution ExplainedSanyam IIT Guwahati · 18:09 · 858 views
Daily Leetcode #2138: Feb 06, 2026 - 3634. Minimum Removals to Balance ArrayProgramming Live with Larry · 10:25 · 410 views
Minimum Removals to Balance Array | LeetCode 3634 - Pythonimpoldev · 9:30 · 357 views
LeetCode 3634. Minimum Removals to Balance Array | Two Pointer | Sorting | Medium | O(NLogN)Leet's Code · 20:29 · 340 views
3634. Minimum Removals to Balance Array | Leetcode Biweekly Contest 162Break and Build · 13:07 · 337 views
Minimum Removals to Balance Array | LeetCode 3634 | Java Code | Developer CoderDeveloper Coder · 11:11 · 316 views
3634. Minimum Removals to Balance Array (Leetcode Medium)Programming Live with Larry · 5:08 · 264 views
Leetcode 3634. Minimum Removals to Balance ArrayCode Maestro Rtj · 8:45 · 137 views
The problem
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] = 5to getnums = [2, 1]. - Now
max = 2,min = 1andmax <= min * kas2 <= 1 * 2. Thus, the answer is 1.
Example 2:
Input: nums = [1,6,2,9], k = 3
Output: 2
Explanation:
- Remove
nums[0] = 1andnums[3] = 9to getnums = [6, 2]. - Now
max = 6,min = 2andmax <= min * kas6 <= 2 * 3. Thus, the answer is 2.
Example 3:
Input: nums = [4,6], k = 2
Output: 0
Explanation:
- Since
numsis already balanced as6 <= 4 * 2, no elements need to be removed.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 1091 <= 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.
class Solution:
def minRemoval(self, nums: List[int], k: int) -> int:
nums.sort()
cnt = 0
for i, x in enumerate(nums):
j = bisect_right(nums, k * x)
cnt = max(cnt, j - i)
return len(nums) - cntclass Solution {
public int minRemoval(int[] nums, int k) {
Arrays.sort(nums);
int cnt = 0;
int n = nums.length;
for (int i = 0; i < n; ++i) {
int j = n;
if (1L * nums[i] * k <= nums[n - 1]) {
j = Arrays.binarySearch(nums, nums[i] * k + 1);
j = j < 0 ? -j - 1 : j;
}
cnt = Math.max(cnt, j - i);
}
return n - cnt;
}
}class Solution {
public:
int minRemoval(vector<int>& nums, int k) {
ranges::sort(nums);
int cnt = 0;
int n = nums.size();
for (int i = 0; i < n; ++i) {
int j = n;
if (1LL * nums[i] * k <= nums[n - 1]) {
j = upper_bound(nums.begin(), nums.end(), 1LL * nums[i] * k) - nums.begin();
}
cnt = max(cnt, j - i);
}
return n - cnt;
}
};function minRemoval(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let cnt = 0;
for (let i = 0; i < n; ++i) {
let j = n;
if (nums[i] * k <= nums[n - 1]) {
const target = nums[i] * k + 1;
j = _.sortedIndexBy(nums, target, x => x);
}
cnt = Math.max(cnt, j - i);
}
return n - cnt;
}func minRemoval(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
cnt := 0
for i := 0; i < n; i++ {
j := n
if int64(nums[i])*int64(k) <= int64(nums[n-1]) {
target := int64(nums[i])*int64(k) + 1
j = sort.Search(n, func(x int) bool {
return int64(nums[x]) >= target
})
}
cnt = max(cnt, j-i)
}
return n - cnt
}impl Solution {
pub fn min_removal(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort();
let mut cnt = 0;
let n = nums.len();
for i in 0..n {
let mut j = n;
let target = nums[i] as i64 * k as i64;
if target <= nums[n - 1] as i64 {
j = nums.partition_point(|&x| x as i64 <= target);
}
cnt = cnt.max(j - i);
}
(n - cnt) as i32
}
}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.
class Solution:
def minRemoval(self, nums: List[int], k: int) -> int:
nums.sort()
ans = n = len(nums)
r = 0
for l in range(n):
while r < n and nums[r] <= nums[l] * k:
r += 1
ans = min(ans, n - (r - l))
return ansclass Solution {
public int minRemoval(int[] nums, int k) {
Arrays.sort(nums);
int n = nums.length;
int ans = n;
int r = 0;
for (int l = 0; l < n; l++) {
while (r < n && nums[r] <= (long) nums[l] * k) {
r++;
}
ans = Math.min(ans, n - (r - l));
}
return ans;
}
}class Solution {
public:
int minRemoval(vector<int>& nums, int k) {
ranges::sort(nums);
int n = nums.size();
int ans = n;
int r = 0;
for (int l = 0; l < n; l++) {
while (r < n && nums[r] <= (long long) nums[l] * k) {
r++;
}
ans = min(ans, n - (r - l));
}
return ans;
}
};function minRemoval(nums: number[], k: number): number {
nums.sort((a, b) => a - b);
const n = nums.length;
let ans = n;
let r = 0;
for (let l = 0; l < n; l++) {
while (r < n && nums[r] <= nums[l] * k) {
r++;
}
ans = Math.min(ans, n - (r - l));
}
return ans;
}func minRemoval(nums []int, k int) int {
sort.Ints(nums)
n := len(nums)
ans := n
r := 0
for l := 0; l < n; l++ {
for r < n && nums[r] <= nums[l]*k {
r++
}
ans = min(ans, n-(r-l))
}
return ans
}impl Solution {
pub fn min_removal(mut nums: Vec<i32>, k: i32) -> i32 {
nums.sort();
let n = nums.len();
let mut ans = n;
let mut r = 0;
let k = k as i64;
for l in 0..n {
while r < n && nums[r] as i64 <= nums[l] as i64 * k {
r += 1;
}
ans = ans.min(n - (r - l));
}
ans as i32
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Sorting + Binary Search | – |
| Sorting + Two Pointers | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting + Binary Search | O(n log n) | O(1) | Good when you want a straightforward implementation using ordered lookups for each starting index. |
| Sorting + Two Pointers | O(n log n) | O(1) | Preferred approach after sorting when scanning for the largest valid window efficiently. |
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.