LeetCode 2171 - Removing Minimum Number of Magic Beans

LeetCode Problem 2171

Difficulty: 🟡 Medium
Topics: Array, Greedy, Sorting, Enumeration, Prefix Sum

Solution

Problem Understanding

The problem asks us to remove beans from bags in such a way that all non-empty bags have the same number of beans while minimizing the total number of beans removed. Each element in the input array beans represents a bag with a positive number of beans. We are allowed to remove any number of beans from a bag, including all beans, but once a bean is removed, it cannot be added to another bag.

The goal is to return the minimum total number of beans removed so that all remaining non-empty bags have the same number of beans. The constraints 1 <= beans.length <= 10^5 and 1 <= beans[i] <= 10^5 indicate that we need a solution that is linearithmic or better, as a naive approach will be too slow.

Important edge cases include arrays where all elements are the same, arrays with only one bag, arrays with many small and one large element, or arrays that are already sorted in ascending or descending order. The problem guarantees all numbers are positive, so we never have to handle zeros initially.

Approaches

The brute-force approach would be to try making each distinct bean count the target number for all non-empty bags. For each target value x, we calculate the total number of beans to remove to make all non-empty bags equal to x. This works but is inefficient because for each target we must iterate over the entire array, resulting in O(n^2) in the worst case if all beans are distinct.

The key observation for an optimal solution is that after sorting the array, if we choose a bag at position i in the sorted array as the target for all non-empty bags, we only need to remove all beans from bags before i and reduce all bags from i onward to match beans[i]. Using prefix sums or a running total allows us to compute the total removal efficiently, reducing the complexity to O(n log n) due to sorting.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^2)	O(1)	Try each possible target value and compute total removal
Optimal	O(n log n)	O(1)	Sort array and calculate removal using running sums

Algorithm Walkthrough

1. Sort the input array beans in ascending order. Sorting ensures that smaller values come first, which makes it easy to compute the beans we need to remove from smaller bags.
2. Compute the total sum of all beans. This will help in calculating the number of beans removed when choosing a target bag value.
3. Initialize a variable min_removal to infinity. This will store the minimum number of beans removed across all possible targets.
4. Iterate over each index i in the sorted array. Consider beans[i] as the target value for all non-empty bags.
5. For each target beans[i], calculate the total number of beans to remove using the formula: total_sum - (beans[i] * (n - i)). Here, (n - i) is the number of bags that will be kept non-empty, and we remove all beans from bags before i.
6. Update min_removal if the current removal count is smaller.
7. Return min_removal after checking all possible targets.

Why it works: Sorting ensures that we consider the smallest bag first for removal, and using the total sum allows us to efficiently compute how many beans must be removed from all other bags to match a given target. This guarantees we find the minimum removal.

Python Solution

from typing import List

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        total_sum = sum(beans)
        n = len(beans)
        min_removal = float('inf')
        
        for i, b in enumerate(beans):
            # Total removal = sum of beans removed from smaller bags + beans removed to match target in bigger bags
            removal = total_sum - b * (n - i)
            min_removal = min(min_removal, removal)
        
        return min_removal

The Python implementation first sorts the array, calculates the total sum, and iterates over each potential target. For each target, it calculates how many beans would be removed if all remaining non-empty bags are reduced to this target value. The minimum across all targets is returned.

Go Solution

import "sort"

func minimumRemoval(beans []int) int64 {
    sort.Ints(beans)
    var total int64
    for _, b := range beans {
        total += int64(b)
    }

    var minRemoval int64 = total
    n := len(beans)
    for i, b := range beans {
        removal := total - int64(b)*(int64(n-i))
        if removal < minRemoval {
            minRemoval = removal
        }
    }
    return minRemoval
}

The Go solution mirrors the Python version. We use int64 to prevent overflow due to the sum of large numbers. Sorting is done with the built-in sort.Ints. The total sum is computed as int64, and the minimum removal is updated similarly.

Worked Examples

Example 1: beans = [4,1,6,5]

Sort: [1,4,5,6], sum = 16

i	beans[i]	Remaining Bags	Removal = total - beans[i]*(n-i)
0	1	[1,4,5,6]	16 - 1*4 = 12
1	4	[4,5,6]	16 - 4*3 = 4
2	5	[5,6]	16 - 5*2 = 6
3	6	[6]	16 - 6*1 = 10

Minimum removal = 4

Example 2: beans = [2,10,3,2]

Sort: [2,2,3,10], sum = 17

i	beans[i]	Remaining Bags	Removal = total - beans[i]*(n-i)
0	2	[2,2,3,10]	17 - 2*4 = 9
1	2	[2,3,10]	17 - 2*3 = 11
2	3	[3,10]	17 - 3*2 = 11
3	10	[10]	17 - 10*1 = 7

Minimum removal = 7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates; the iteration over n elements is O(n)
Space	O(1)	In-place sorting, constant extra space except input storage

Sorting is the primary cost, and the one-pass iteration efficiently computes the removal without extra storage.

Test Cases

# Provided examples
assert Solution().minimumRemoval([4,1,6,5]) == 4  # Example 1
assert Solution().minimumRemoval([2,10,3,2]) == 7  # Example 2

# Edge cases
assert Solution().minimumRemoval([1]) == 0  # Single element, nothing to remove
assert Solution().minimumRemoval([5,5,5,5]) == 0  # All same, no removal needed
assert Solution().minimumRemoval([1,2,3,4,5]) == 6  # Increasing sequence
assert Solution().minimumRemoval([10,1,1,1]) == 3  # One large, multiple small
assert Solution().minimumRemoval([100000]) == 0  # Maximum single element

Test	Why
[4,1,6,5]	Tests general scenario
[2,10,3,2]	Tests mixture of small and large numbers
[1]	Tests minimum size array
[5,5,5,5]	Tests all equal
[1,2,3,4,5]	Tests increasing sequence
[10,1,1,1]	Tests one large and several small
[100000]	Tests maximum single element

Edge Cases

One important edge case is an array of length 1. The solution must handle this without error and return 0 because no removal is needed. Another edge case is when all elements are equal; again, the removal must be zero. Arrays with one very large element and many small elements are tricky because the minimum removal might involve removing all smaller elements rather than reducing the large one. Sorting and calculating removal as described ensures all these cases are handled correctly.