Leetcode #2171: Removing Minimum Number of Magic Beans
In this guide, we solve Leetcode #2171 Removing Minimum Number of Magic Beans in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
You are given an array of positive integers beans, where each integer represents the number of magic beans found in a particular magic bag. Remove any number of beans (possibly none) from each bag such that the number of beans in each remaining non-empty bag (still containing at least one bean) is equal.
Quick Facts
- Difficulty: Medium
- Premium: No
- Tags: Greedy, Array, Enumeration, Prefix Sum, Sorting
Intuition
A locally optimal choice leads to a globally optimal result for this structure.
That means we can commit to decisions as we scan without backtracking.
Approach
Sort or preprocess if needed, then repeatedly take the best available local choice.
Maintain the minimal state necessary to validate the greedy decision.
Steps:
- Sort or preprocess as needed.
- Iterate and pick the best local option.
- Track the current solution.
Example
Input: beans = [4,1,6,5]
Output: 4
Explanation:
- 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.
Python Solution
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))
Complexity
The time complexity is , and the space complexity is . The space complexity is .
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.