LC-1648 Medium LeetCode

1648. Sell Diminishing-Valued Colored Balls

Array Math Binary Search Greedy Sorting Heap (Priority Queue)

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 30% Topics: Array, Math, Binary Search, Greedy, Sorting, Heap (Priority Queue)

Reading material

Arrays & Hashing 12 min Math & Geometry 12 min Binary Search 12 min

Reference solution (spoiler · python)

# Time:  O(nlogm), m is the max of inventory, n is the size of inventory
# Space: O(1)

class Solution(object):
    def maxProfit(self, inventory, orders):
        """
        :type inventory: List[int]
        :type orders: int
        :rtype: int
        """
        MOD = 10**9+7
        def check(inventory, orders, x):
            return count(inventory, x) > orders
        
        def count(inventory, x):
            return sum(count-x+1 for count in inventory if count >= x)

        left, right = 1, max(inventory)
        while left <= right:
            mid = left + (right-left)//2
            if not check(inventory, orders, mid):
                right = mid-1
            else:
                left = mid+1
        # assert(orders-count(inventory, left) >= 0)
        return (sum((left+cnt)*(cnt-left+1)//2 for cnt in inventory if cnt >= left) +
                (left-1)*(orders-count(inventory, left)))% MOD

Solution from kamyu104/LeetCode-Solutions · MIT