MediumNo. 1648
Sell Diminishing-Valued Colored Balls — LeetCode 1648 Python Solution
- Pattern
- Heap / Priority Queue
- Topics
- Greedy, Array, Math, Binary Search, Sorting, 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
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
- Time
- O(log n) or O(n log n)
- Space · auxiliary
- O(1)
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
| No. | Problem | Difficulty |
|---|---|---|
| 2333 | Minimum Sum of Squared Difference | Medium |
| 2790 | Maximum Number of Groups With Increasing Length | Hard |
| 2967 | Minimum Cost to Make Array Equalindromic | Medium |
| 0378 | Kth Smallest Element in a Sorted Matrix | Medium |
| 1268 | Search Suggestions System | Medium |
| 1337 | The K Weakest Rows in a Matrix | Easy |
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.