Sell Diminishing-Valued Colored Balls — LeetCode 1648 Python Solution
MediumGreedyArrayMathBinary SearchSortingHeap (Priority Queue)
- Problem
- #1648
- Pattern
- Heap / Priority Queue
- Reading time
- 5 min
- Source
- leetcode.com
The problem
You have an inventory of different colored balls, and there is a customer that wants orders balls of any color. The customer weirdly values the colored balls.
Example
- Input
- inventory = [2,5], orders = 4
- Output
- 14
- Explanation
- Sell the 1st color 1 time (2) and the 2nd color 3 times (5 + 4 + 3).
Python solution
Python
class Solution:
def maxProfit(self, inventory: List[int], orders: int) -> int:
inventory.sort(reverse=True)
mod = 10**9 + 7
ans = i = 0
n = len(inventory)
while orders > 0:
while i < n and inventory[i] >= inventory[0]:
i += 1
nxt = 0
if i < n:
nxt = inventory[i]
cnt = i
x = inventory[0] - nxt
tot = cnt * x
if tot > orders:
decr = orders // cnt
a1, an = inventory[0] - decr + 1, inventory[0]
ans += (a1 + an) * decr // 2 * cnt
ans += (inventory[0] - decr) * (orders % cnt)
else:
a1, an = nxt + 1, inventory[0]
ans += (a1 + an) * x // 2 * cnt
inventory[0] = nxt
orders -= tot
ans %= mod
return ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(log n) or O(n log n) |
| Space | O(1) auxiliary |
Pattern: Heap / Priority Queue
Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1648. Sell Diminishing-Valued Colored Balls is filed here because LeetCode tags it Heap (Priority Queue), which is the vocabulary this hub collects.
The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.
Related problems
LeetCode 2333Minimum Sum of Squared DifferenceMediumLeetCode 2790Maximum Number of Groups With Increasing LengthHardLeetCode 2967Minimum Cost to Make Array EqualindromicMediumLeetCode 378Kth Smallest Element in a Sorted MatrixMediumLeetCode 1268Search Suggestions SystemMediumLeetCode 1337The K Weakest Rows in a MatrixEasy
Frequently asked questions
- How hard is LeetCode 1648. Sell Diminishing-Valued Colored Balls?
- LeetCode 1648. Sell Diminishing-Valued Colored Balls is rated Medium on LeetCode.
- What topics does LeetCode 1648. Sell Diminishing-Valued Colored Balls cover?
- LeetCode 1648. Sell Diminishing-Valued Colored Balls is tagged Greedy, Array, Math, Binary Search, Sorting and Heap (Priority Queue) on LeetCode.