Watch 10 video solutions for Sell Diminishing-Valued Colored Balls, a medium level problem involving Array, Math, Binary Search. This walkthrough by Fraz has 10,770 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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. Each colored ball's value is the number of balls of that color you currently have in your inventory. For example, if you own 6 yellow balls, the customer would pay 6 for the first yellow ball. After the transaction, there are only 5 yellow balls left, so the next yellow ball is then valued at 5 (i.e., the value of the balls decreases as you sell more to the customer).
You are given an integer array, inventory, where inventory[i] represents the number of balls of the ith color that you initially own. You are also given an integer orders, which represents the total number of balls that the customer wants. You can sell the balls in any order.
Return the maximum total value that you can attain after selling orders colored balls. As the answer may be too large, return it modulo 109 + 7.
Example 1:
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). The maximum total value is 2 + 5 + 4 + 3 = 14.
Example 2:
Input: inventory = [3,5], orders = 6 Output: 19 Explanation: Sell the 1st color 2 times (3 + 2) and the 2nd color 4 times (5 + 4 + 3 + 2). The maximum total value is 3 + 2 + 5 + 4 + 3 + 2 = 19.
Constraints:
1 <= inventory.length <= 1051 <= inventory[i] <= 1091 <= orders <= min(sum(inventory[i]), 109)Problem Overview: You are given an inventory where each number represents how many balls of a color you have. The value of a ball equals the current count of that color, and every sale decreases its value by 1. The goal is to sell exactly orders balls while maximizing total profit.
Approach 1: Greedy with Priority Queue (Heap) (Time: O(orders log n), Space: O(n))
This approach always sells the most valuable ball available. Store all inventory counts in a max heap. Each step removes the largest value, adds it to profit, decreases it by one, and pushes it back if the value is still positive. The greedy idea works because selling higher-valued balls earlier always increases total revenue. A heap ensures efficient retrieval of the current maximum. This approach is intuitive and easy to implement using a heap (priority queue), though it can be slower when orders is very large because every sale requires a heap operation.
Approach 2: Binary Search + Arithmetic Series (Time: O(n log maxValue), Space: O(1))
A more optimized strategy avoids simulating every sale. Instead, observe that selling balls from a color produces a decreasing sequence like k + (k-1) + (k-2) .... Use binary search to find a threshold value x such that selling all balls valued above x satisfies or nearly satisfies the required number of orders. Once the threshold is found, compute the profit using arithmetic series formulas instead of iterating per sale. For each inventory value greater than x, sum the range value ... x+1. Remaining orders at value x are added afterward. This reduces the work dramatically and is the typical optimal solution in interviews.
The solution also benefits from sorting or iterating the array of inventory counts while calculating how many balls exist above the threshold. The mathematical insight transforms a potentially billions-step simulation into a few arithmetic operations.
Recommended for interviews: The binary search approach is what interviewers usually expect because it demonstrates strong reasoning with greedy strategy and arithmetic series optimization. Implementing the heap solution first shows correct intuition about always selling the highest-value ball, but recognizing the need to aggregate ranges with math separates a good solution from a great one.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Greedy with Max Heap | O(orders log n) | O(n) | Good for understanding the greedy idea and when orders are relatively small |
| Binary Search + Arithmetic Series | O(n log maxValue) | O(1) | Optimal solution when orders can be very large and simulation would be too slow |