#2171

Medium

auto_awesomeGreedy choice plus invariant validation

LeetCode Problem Workspace

Removing Minimum Number of Magic Beans

Determine the minimum beans to remove so all remaining non-empty bags have equal beans using a greedy approach.

array greedy sorting enumeration prefix sum

Problem Statement

You are given an array of positive integers beans, where each element represents the number of magic beans in a specific bag. You may remove any number of beans from any bag, including removing all beans from some bags, but removed beans cannot be returned.

Your task is to remove the minimum number of beans so that all non-empty bags have the same number of beans. Return the total count of beans removed to achieve this goal.

Examples

Example 1

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

Output: 4

We remove 1 bean from the bag with only 1 bean. This results in the remaining bags: [4,0,6,5]
Then we remove 2 beans from the bag with 6 beans. This results in the remaining bags: [4,0,4,5]
Then we remove 1 bean from the bag with 5 beans. This results in the remaining bags: [4,0,4,4] We removed a total of 1 + 2 + 1 = 4 beans to make the remaining non-empty bags have an equal number of beans. There are no other solutions that remove 4 beans or fewer.

Example 2

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

Output: 7

We remove 2 beans from one of the bags with 2 beans. This results in the remaining bags: [0,10,3,2]
Then we remove 2 beans from the other bag with 2 beans. This results in the remaining bags: [0,10,3,0]
Then we remove 3 beans from the bag with 3 beans. This results in the remaining bags: [0,10,0,0] We removed a total of 2 + 2 + 3 = 7 beans to make the remaining non-empty bags have an equal number of beans. There are no other solutions that removes 7 beans or fewer.

Constraints

1 <= beans.length <= 105
1 <= beans[i] <= 105

Solution Approach

Sort the beans array

Start by sorting the beans array in ascending order. Sorting allows the greedy selection of the smallest bags to empty first, which aligns with the invariant that remaining bags must equal the target bean count.

Iteratively calculate removals for each target

For each position i in the sorted array, consider beans[i] as the target number of beans for remaining non-empty bags. Remove all beans from bags before i and reduce beans in bags after i to match beans[i]. Keep track of the minimum total removals.

Select the minimum total removal

After evaluating each target, return the smallest total removal. This ensures the solution uses greedy choice plus invariant validation to minimize removals while maintaining equal beans in remaining bags.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Sorting the array takes O(n log n) and iterating through each element to calculate total removals takes O(n). Overall time complexity is O(n log n). Space complexity is O(1) extra or O(n) if storing prefix sums.

What Interviewers Usually Probe

Look for a strategy that reduces the problem to a sorted array and considers each unique bean count as a target.
Ask candidates how removing the smallest bags first maintains the invariant for remaining equal bags.
Check if the candidate considers cumulative sums or prefix sums to compute removals efficiently.

Common Pitfalls or Variants

Common pitfalls

Failing to sort the array before applying the greedy choice leads to incorrect minimal removal calculation.
Removing beans without considering the invariant that remaining bags must all have equal beans.
Overcomplicating by trying to adjust bags in arbitrary order instead of emptying smallest bags first.

Follow-up variants

Modify the problem to maximize remaining beans instead of minimizing removals using the same greedy invariant approach.
Consider cases where only a subset of bags must match a target, requiring selective greedy removal.
Introduce multiple bean types per bag and require equality per type, extending the prefix sum and greedy logic.

FAQ

What is the key pattern in Removing Minimum Number of Magic Beans?

The problem follows a greedy choice plus invariant validation pattern, where smallest bags are emptied first to maintain equality.

How do I decide which bags to empty first?

Always start with the bags containing the fewest beans, as emptying them first minimizes total removals while keeping the remaining bags equal.

Can prefix sums speed up the solution?

Yes, prefix sums allow efficient calculation of total beans removed from bags before and after each target position, improving O(n) computation after sorting.

Does the solution work for large arrays up to 10^5 elements?

Yes, sorting and prefix sum computation scales efficiently, meeting constraints of 1 <= beans.length <= 105.

Is it ever optimal to leave more than one smallest bag non-empty?

No, keeping multiple smallest bags increases total removals; the greedy invariant ensures minimal removal by emptying the smallest bags first.

terminal

Solution

Solution 1: Sorting + Enumeration

We can sort all the beans in the bags in ascending order, and then enumerate the number of beans $beans[i]$ in each bag as the final number of beans in the bag. The total remaining number of beans is $beans[i] \times (n - i)$, so the number of beans that need to be taken out is $s - beans[i] \times (n - i)$, where $s$ is the total number of beans in all bags. We need to find the minimum number of beans that need to be taken out among all schemes.

1

2

3

4

5

class Solution:
    def minimumRemoval(self, beans: List[int]) -> int:
        beans.sort()
        s, n = sum(beans), len(beans)
        return min(s - x * (n - i) for i, x in enumerate(beans))

Continue Practicing

#2234 maximum total beauty of the gardens #2271 maximum white tiles covered by a carpet #2389 longest subsequence with limited sum