LC-2171 Medium LeetCode

2171. Removing Minimum Number of Magic Beans

Array Greedy Sorting Enumeration Prefix Sum

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 44% Topics: Array, Greedy, Sorting, Enumeration, Prefix Sum

Reading material

Arrays & Hashing 12 min Greedy 11 min Sorting 13 min

Reference solution (spoiler · python)

# Time:  O(nlogn)
# Space: O(1)

# math
class Solution(object):
    def minimumRemoval(self, beans):
        """
        :type beans: List[int]
        :rtype: int
        """
        beans.sort()
        return sum(beans) - max(x*(len(beans)-i)for i, x in enumerate(beans))

Solution from kamyu104/LeetCode-Solutions · MIT