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)This approach uses a max-heap (priority queue) to always sell the highest valued balls first.
Steps:
10^9 + 7.The algorithm uses a max-heap to store the values of colored balls in descending order. It repeatedly pops the highest value, sells a number of balls equal to the difference between the current max and the next max, adjusts the orders remaining, and calculates the total value gained. The heap is adjusted accordingly to reflect the new ball count.
JavaScript
Time Complexity: O(n+mlog n) where n is the number of colors and m is the number of orders.
Space Complexity: O(n) for storing the heap and other auxiliary structures.
This approach uses binary search to determine the threshold at which we should stop selling each ball to ensure maximum profit.
Steps:
This C++ solution determines the threshold price at which to stop selling balls using a binary search over the maximum number of balls that can be sold. The sorted inventory helps easily determine levels at which ball count must diminish. The search seeks to balance ball sale count against the maximum price achievable.
Java
Time Complexity: O(nlog m) where n is the number of colors and m is the maximum ball count.
Space Complexity: O(1) aside from input storage.
| Approach | Complexity |
|---|---|
| Approach 1: Greedy with Priority Queue | Time Complexity: O(n+mlog n) where n is the number of colors and m is the number of orders. |
| Approach 2: Binary Search | Time Complexity: O(nlog m) where n is the number of colors and m is the maximum ball count. |
How much Money I made as a Developer • NeetCodeIO • 320,904 views views
Watch 9 more video solutions →Practice Sell Diminishing-Valued Colored Balls with our built-in code editor and test cases.
Practice on FleetCode