Minimum Removals to Balance Array — Algorithm Visualization & Coding Challenge

3634. Minimum Removals to Balance Array

Difficulty: Medium
Topics: Array, Two Pointers, Sorting

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 always balanced because its maximum and minimum elements are equal.

Examples

Example 1

Input

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

Output

1

Explanation
Remove 5 → remaining array: [2, 1]

• min = 1
• max = 2
• (2 ≤ 1 × 2) → balanced

Example 2

Input

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

Output

2

Explanation
Remove 1 and 9 → remaining array: [6, 2]

• min = 2
• max = 6
• (6 ≤ 2 × 3) → balanced

Example 3

Input

nums = [4, 6], k = 2

Output

0

Explanation
The array is already balanced because (6 ≤ 4 × 2).

Constraints

• 1 ≤ nums.length ≤ 10^5
• 1 ≤ nums[i] ≤ 10^9
• 1 ≤ k ≤ 10^5 `

import java.util.*;

public class Main {

public static int minimumRemovals(int[] nums, int k) {
    Arrays.sort(nums);
    int n = nums.length;

    int left = 0;
    int maxWindow = 1;

    for (int right = 0; right < n; right++) {
        while ((long) nums[right] > (long) nums[left] * k) {
            left++;
        }
        maxWindow = Math.max(maxWindow, right - left + 1);
    }

    return n - maxWindow;
}

public static void main(String[] args) {

    // 🔹 Hardcoded Input
    int[] nums = {1, 6, 2, 9};
    int k = 3;

    int result = minimumRemovals(nums, k);
    System.out.println("Minimum removals: " + result);
}

}