MediumArrayMathBinary SearchGreedySortingHeapUpdated Sep 2026

1648. Sell Diminishing-Valued Colored Balls

Asked at Goldman Sachs

Difficulty

Medium

Time

O(n log n)

Space

O(1)

Pattern

Array

Companies

1

Problem

You own balls of several colors. inventory[i] is how many balls you have of color i. A customer wants to buy exactly orders balls in total, and you may choose the colors in any order.

The price of a ball is the number of balls of that color still in your inventory at the moment you sell it. So if you have 6 yellow balls, the first yellow ball sells for 6, the next for 5, and so on. Selling a ball always lowers the price of the next ball of the same color by 1.

Return the maximum total money you can collect from selling exactly orders balls, taken modulo 10^9 + 7.

Price drops as you sell

inventory2501Color 1 has 2 balls, color 2 has 5 balls — start withthe taller pilesell color 2 → 5sell color 2 → 4sell color 2 → 3sell color 1 → 24 orders: 5 + 4 + 3 + 2 = 14 is the best total
Each color has its own price ladder, and you pick the highest rung still available.

Constraints

  • ●1 <= inventory.length <= 10^5
  • ●1 <= inventory[i] <= 10^9
  • ●1 <= orders <= min(sum(inventory[i]), 10^9)

Examples

Example 1
Inputinventory = [2,5], orders = 4
Output14
WhySell 1 ball of the first color for 2, then 3 balls of the second color for 5, 4 and 3. Total is 2 + 5 + 4 + 3 = 14. Selling the second color first would give less.
Example 2
Inputinventory = [3,5], orders = 6
Output19
WhySell 2 balls of the first color (3 + 2) and 4 balls of the second color (5 + 4 + 3 + 2). Total is 3 + 2 + 5 + 4 + 3 + 2 = 19.

Asked At

1 companies
CompanyDifficulty
Goldman SachsMediumView all Goldman Sachs questions →

How to Think About It

1

Greedy is optimal: each sale should take the color with the highest current value. A max-heap does that, but popping one ball at a time is O(orders log n) — too slow.

2

Key insight: sort counts in descending order. The top w colors will be sold down together from their value to the next distinct value, like peeling horizontal layers off a skyline.

3

Selling all top w colors from value hi down to (but not including) lo earns w * (lo+1 + ... + hi) and uses w * (hi - lo) orders.

4

When the remaining orders do not cover a full layer, sell full = orders // w complete levels from each of the w colors, then orders % w more balls at the next value.

5

Compute series sums with (a + b) * (b - a + 1) / 2 and apply the modulo carefully in fixed-width languages.

Optimal Approach

Step 1: Sort inventory descending and append 0.
Step 2: For i from 0 with width w = i + 1:
hi = inv[i], lo = inv[i+1]. If hi == lo, continue.
If w * (hi - lo) <= orders: add w * series(lo+1, hi); orders -= w * (hi - lo).
Else: full = orders // w, rem = orders % w; add w * series(hi-full+1, hi) + rem * (hi - full); stop.
Stop when orders == 0.
Step 3: Return the total mod 10^9 + 7.

Time: O(n log n). Space: O(1) extra.

Peel layers off the sorted skyline

sorted520012hilow = 1, hi = 5, lo = 2: one layer of height 3 costs 1*3= 3 orderssorted220012hiloAfter the layer, both piles sit at 2 and 1 order isleftlayer value = w * (lo+1 + ... + hi)layer cost = w * (hi - lo)leftover = orders % w balls at hi - full
Sort descending, then sell the top w colors down to the next distinct level as one block.
ComplexityTime O(n log n)Space O(1)Sorting the inventory dominates; the layer-by-layer loop afterwards is O(n) and uses only a few variables.

What Trips People Up in Real Interviews

1

Simulating one sale at a time with a heap. orders can be 10^9.

2

Overflow in C++/Java: compute each series sum in 64-bit, reduce it mod 10^9 + 7, then multiply by the width.

3

Forgetting the partial layer: when orders run out mid-layer, some colors are sold one level deeper than others.

4

Not appending a 0 sentinel, which makes the last layer an edge case.

Solution Code

O(n log n) time
def maxProfit(inventory, orders):
    MOD = 10**9 + 7
    inv = sorted(inventory, reverse=True) + [0]

    def series(a, b):
        return (a + b) * (b - a + 1) // 2

    total = 0
    for i in range(len(inv) - 1):
        w = i + 1
        hi, lo = inv[i], inv[i + 1]
        if hi == lo:
            continue
        if w * (hi - lo) <= orders:
            total += w * series(lo + 1, hi)
            orders -= w * (hi - lo)
        else:
            full, rem = divmod(orders, w)
            total += w * series(hi - full + 1, hi) + rem * (hi - full)
            orders = 0
        if orders == 0:
            break
    return total % MOD

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Sell Diminishing-Valued Colored Balls problem?

Sell Diminishing-Valued Colored Balls gives you counts of balls per color; selling a ball earns its color's current count, and the count then drops by one. Given `orders` total sales, maximize the revenue modulo `10^9 + 7`. Greedily sell the most plentiful color, but do it in bulk with arithmetic series, because `orders` can be `10^9`.

How do you solve Sell Diminishing-Valued Colored Balls?

The optimal approach runs in O(n log n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Sell Diminishing-Valued Colored Balls?

Sell Diminishing-Valued Colored Balls is asked at Goldman Sachs. It is a medium difficulty problem.

What are common mistakes on Sell Diminishing-Valued Colored Balls?
  • Simulating one sale at a time with a heap. `orders` can be `10^9`.
  • Overflow in C++/Java: compute each series sum in 64-bit, reduce it mod `10^9 + 7`, then multiply by the width.
  • Forgetting the partial layer: when orders run out mid-layer, some colors are sold one level deeper than others.
  • Not appending a 0 sentinel, which makes the last layer an edge case.