Sell Diminishing-Valued Colored Balls solution and explanation
9 more videos on this problem
Leetcode 1648 Sell Diminishing Valued Colored BallsFraz · 25:59 · 11K views
LeetCode 1648. Sell Diminishing-Valued Colored Balls | PythonAH Tech · 9:00 · 5K views
花花酱 LeetCode 1648. Sell Diminishing-Valued Colored Balls - 刷题找工作 EP368Hua Hua · 16:40 · 4K views
Amazon Coding Interview Question | Leetcode 1648 | Sell Diminishing-Valued Colored BallsWorkWithGoogler · 8:47 · 3K views
LeetCode 1648. Sell Diminishing-Valued Colored BallsHappy Coding · 29:36 · 3K views
1648. Sell Diminishing-Valued Colored Balls (Leetcode Medium)Programming Live with Larry · 36:49 · 1K views
【每日一题】1648. Sell Diminishing-Valued Colored Balls, 11/9/2020Huifeng Guan · 45:01 · 967 views
Sell Diminishing-Valued Colored Balls | OA series | Leetcode 1648Sanyam IIT Guwahati · 16:37 · 778 views
大壮刷题 - LeetCode 1648. Sell Diminishing-Valued Colored Balls, Greedy, Math大壮刷题 · 10:33 · 290 views
LeetCode - Medium - Sell Diminishing-Valued Colored Balls - v2Yasin Aydin · 9:39 · 224 views
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. 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)
Approach overview
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 1: Approach 1: Greedy with Priority Queue
This approach uses a max-heap (priority queue) to always sell the highest valued balls first.
Steps:
- Insert all inventory values into a max-heap.
- While orders remain, pop the largest value from the heap, sell it, and push the remaining (value - 1) back into the heap.
- Keep track of the total value sold and reduce the number of orders after each sale.
- Finally, return the total value modulo
10^9 + 7.
import heapq
MOD = 10**9 + 7
def maxProfit(inventory, orders):
max_heap = [-x for x in inventory]
heapq.heapify(max_heap)
total_value = 0
while orders > 0:
current_max = -heapq.heappop(max_heap)
if max_heap:
next_max = -max_heap[0]
else:
next_max = 0
count = min(orders, current_max - next_max)
total_value += count * (current_max + next_max + 1) * (current_max - next_max) // 2
total_value %= MOD
orders -= count * (current_max - next_max)
if next_max < current_max - count:
heapq.heappush(max_heap, -(current_max - count))
return total_valuefunction maxProfit(inventory, orders) {
const MOD = 1e9 + 7;
inventory.sort((a, b) => b - a);
inventory.push(0);
let totalValue = 0;
let idx = 0;
while (orders > 0) {
let current = inventory[idx];
let next = inventory[idx + 1];
let width = idx + 1;
let possibleSell = Math.min(orders, width * (current - next));
let fullPriceCount = Math.floor(possibleSell / width);
let remaining = possibleSell % width;
totalValue += width * (fullPriceCount * (2 * current - fullPriceCount + 1) / 2);
totalValue += remaining * (current - fullPriceCount);
totalValue %= MOD;
orders -= possibleSell;
idx++;
}
return totalValue;
}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.
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.
Approach 2: Approach 2: Binary Search
This approach uses binary search to determine the threshold at which we should stop selling each ball to ensure maximum profit.
Steps:
- Sort the inventory values in descending order.
- Apply binary search to find the maximum price we can sell at while still fulfilling the orders.
- On each iteration of the binary search, calculate the possible number of balls we can sell at a given price.
- Adjust the search range based on whether we can fulfill the order or not.
import java.util.Arrays;
public class Solution {
public int MOD = 1000000007;
public int maxProfit(int[] inventory, int orders) {
Arrays.sort(inventory);
int n = inventory.length;
long totalValue = 0;
for (int i = n - 1; i >= 0 && orders > 0; i--) {
int current = inventory[i];
int next = (i > 0) ? inventory[i - 1] : 0;
int count = n - i;
long sell = (long)(current - next) * count;
if (orders >= sell) {
totalValue += (long)(current + next + 1) * (current - next) / 2 * count;
orders -= sell;
} else {
int fullRound = orders / count;
int remain = orders % count;
totalValue += (long)(current + current - fullRound + 1) * fullRound / 2 * count;
totalValue += (long)remain * (current - fullRound);
orders = 0;
}
totalValue %= MOD;
}
return (int) totalValue;
}
}#include <algorithm>
#include <vector>
using namespace std;
const int MOD = 1e9 + 7;
int maxProfit(vector<int>& inventory, int orders) {
sort(inventory.rbegin(), inventory.rend());
inventory.push_back(0);
int n = inventory.size();
long long totalValue = 0;
for (int i = 0; i < n - 1 && orders > 0; ++i) {
int current = inventory[i];
int next = inventory[i + 1];
int width = i + 1;
long long possibleSell = (long long)width * (current - next);
if (orders >= possibleSell) {
totalValue += (long long)width * (current + next + 1) * (current - next) / 2;
orders -= possibleSell;
} else {
int fullPriceCount = orders / width;
int remaining = orders % width;
totalValue += (long long)width * (current + current - fullPriceCount + 1) * fullPriceCount / 2;
totalValue += (long long)remaining * (current - fullPriceCount);
orders = 0;
}
totalValue %= MOD;
}
return totalValue;
}This Java solution is similar in principle to the C++ version, employing binary searching indirectly through a reduction process based on sorted and iterated inventory levels. Total profit is maximized by ensuring each possible sale uses the optimal price tier.
Time Complexity: O(nlog n) where n is the number of color types, primarily due to sorting.
Space Complexity: O(1) beyond the initial array storage.
Approach 3: Default Approach
func maxProfit(inventory []int, orders int) int {
var mod int = 1e9 + 7
i, n, ans := 0, len(inventory), 0
sort.Ints(inventory)
for i, j := 0, n-1; i < j; i, j = i+1, j-1 {
inventory[i], inventory[j] = inventory[j], inventory[i]
}
for orders > 0 {
for i < n && inventory[i] >= inventory[0] {
i++
}
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 += (a1 - 1) * (orders % cnt)
} else {
a1, an := nxt+1, inventory[0]
ans += (a1 + an) * x / 2 * cnt
inventory[0] = nxt
}
orders -= tot
ans %= mod
}
return ans
}Complexity comparison
| 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 n) where n is the number of color types, primarily due to sorting. |
| Default Approach | – |
Complexity analysis
| 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 |
Frequently asked questions
Is Sell Diminishing-Valued Colored Balls easy or hard?
The problem is rated Medium on LeetCode but can feel closer to Hard if you try to simulate each sale directly. The challenge is recognizing that the values form decreasing sequences and can be summed using arithmetic formulas instead of iterating through every order.
Sell Diminishing-Valued Colored Balls Python/Java solution
Python implementations typically use a heap via heapq (simulating a max heap with negative values) for the greedy approach. Java solutions often implement the optimized binary search method with arithmetic series calculations to avoid simulating every sale.
How to solve Sell Diminishing-Valued Colored Balls in O(n)?
A strictly O(n) solution is not typical because the optimal algorithm uses binary search over the value range, giving O(n log maxValue). However, once the threshold value is determined, the remaining profit calculation for each inventory entry is linear using arithmetic progression formulas.
What is the best approach for Sell Diminishing-Valued Colored Balls?
The most efficient approach uses binary search combined with arithmetic series math. Instead of selling balls one by one, you find a threshold value where all balls above that value are sold. The profit from each range can then be computed using the formula for the sum of consecutive integers. This reduces the complexity to O(n log maxValue) with constant extra space.
Is Sell Diminishing-Valued Colored Balls asked at Google/Amazon/Meta?
This problem tests greedy reasoning, priority queues, and mathematical optimization—topics frequently asked in interviews at companies like Amazon, Google, and Meta. Variants involving selling items with decreasing value or maximizing profit under constraints appear regularly in technical interviews.
What data structure is used in Sell Diminishing-Valued Colored Balls?
The straightforward implementation uses a max heap (priority queue) to always sell the highest-value ball first. The optimized approach relies more on mathematical reasoning with arrays and binary search rather than heavy data structure usage.
What is the time complexity of Sell Diminishing-Valued Colored Balls?
The heap-based greedy solution runs in O(orders log n) time because each sale requires removing and reinserting an element in a priority queue. The optimized binary search approach runs in O(n log maxValue) time by searching for the selling threshold and computing profits using arithmetic series formulas.