Sell Diminishing-Valued Colored Balls: Greedy Leveling Pattern

You have an inventory of colored balls where inventory[i] is the number of balls of color i. A customer wants to buy exactly orders balls. When you sell a ball of color i whose current inventory is k, the value of that sale is k. After the sale, the inventory of that color drops to k - 1. Return the maximum total value you can get from selling exactly orders balls, modulo 10^9 + 7.

This is LeetCode 1648: Sell Diminishing-Valued Colored Balls, a medium problem that looks like it needs a heap simulation but actually yields to a sorting plus greedy leveling approach. The trick is to avoid selling one ball at a time and instead compute bulk sales using arithmetic series.

Why this problem matters

This problem combines greedy thinking with a math optimization. The naive approach of always picking the single most valuable ball and selling it works logically, but it is O(orders * log n) with a heap and can time out when orders reaches 10^9. The real challenge is figuring out how to batch those individual sales into bulk operations.

The greedy leveling pattern that solves this problem shows up in resource allocation scenarios, scheduling problems, and anywhere you need to "flatten" a distribution optimally. If you can level down sorted bars efficiently, you unlock a family of similar problems.

The key insight

Since selling a ball of inventory k gives you value k, you always want to sell from the color with the highest inventory. That is the greedy choice: sell the most valuable ball first.

But instead of popping from a heap one ball at a time, you can sort the inventory in descending order and "level" the bars. Look at the tallest bar (or group of bars at the same height) and calculate how many balls you would sell to bring them all down to the height of the next bar. If you have enough orders, sell that entire chunk and compute the profit using the sum formula for consecutive integers.

Here is the leveling idea:

1. Sort inventory in descending order.
2. Walk through the sorted array. At each step, the first i bars are all at the same height inventory[i-1]. The next bar is at height inventory[i] (or 0 if there is no next bar).
3. To level all i bars from their current height down to the next height, you sell i * (current - next) balls.
4. If you have enough orders left, sell the whole chunk. The profit from leveling one bar from height h down to height t is the sum h + (h-1) + ... + (t+1), which equals (h - t) * (h + t + 1) / 2.
5. If you do not have enough orders for the full chunk, sell as many as you can from the partial level.

The solution

def maxProfit(inventory, orders):
    MOD = 10**9 + 7
    inventory.sort(reverse=True)
    inventory.append(0)
    n = len(inventory)
    profit = 0

    for i in range(n - 1):
        width = i + 1
        current = inventory[i]
        nxt = inventory[i + 1]

        if current == nxt:
            continue

        diff = current - nxt
        total_balls = width * diff

        if total_balls <= orders:
            chunk = diff * (current + nxt + 1) // 2
            profit = (profit + chunk * width) % MOD
            orders -= total_balls
        else:
            full_rows = orders // width
            leftover = orders % width

            if full_rows > 0:
                top = current
                bottom = current - full_rows + 1
                chunk = full_rows * (top + bottom) // 2
                profit = (profit + chunk * width) % MOD

            if leftover > 0:
                profit = (profit + (current - full_rows) * leftover) % MOD

            orders = 0
            break

        if orders == 0:
            break

    return profit % MOD

Here is what each piece does:

1. Sort descending and append a sentinel 0. This ensures we always have a "next height" to level down to.
2. Walk through the sorted array. At index i, there are i + 1 bars all at the same height (because we skip equal neighbors with continue). The width is how many bars we are leveling simultaneously.
3. Check if we can sell the full chunk. If total_balls (the number of balls in this level) fits within remaining orders, we compute the profit for one bar using the arithmetic series formula and multiply by width.
4. Handle the partial level. If we do not have enough orders for the full chunk, we figure out how many complete rows we can afford (full_rows) and how many extra balls go in a partial row (leftover). Each leftover ball is sold at the value current - full_rows.
5. Apply modular arithmetic at every addition to prevent overflow.

Visual walkthrough

Let's trace through inventory = [2, 5], orders = 4.

After sorting we get [5, 2]. The first bar is at height 5, the second at height 2. We level bar 0 from 5 down to 2, selling 3 balls at values 5, 4, 3 for a profit of 12. That uses 3 of our 4 orders. Now both bars are at height 2 and we need 1 more sale. We sell 1 ball at value 2 from the group. Total profit = 14.

Complexity analysis

The leveling pass is linear because you visit each element at most once. The bottleneck is the sort. This is a massive improvement over the O(orders * log n) heap simulation, especially when orders can reach 10^9.

The building blocks

This problem is built on two reusable patterns that CodeBricks drills independently.

1. Greedy leveling with arithmetic series

The pattern of "leveling" sorted values down in bulk rather than processing one unit at a time. You sort, then at each step you compute how many units fit in the current level and use the arithmetic series sum to calculate the total value.

values.sort(reverse=True)
values.append(0)
result = 0
for i in range(len(values) - 1):
    width = i + 1
    diff = values[i] - values[i + 1]
    if diff == 0:
        continue
    total = width * diff
    if total <= budget:
        result += width * diff * (values[i] + values[i + 1] + 1) // 2
        budget -= total
    else:
        full = budget // width
        leftover = budget % width
        result += width * full * (values[i] + values[i] - full + 1) // 2
        result += leftover * (values[i] - full)
        break

This same skeleton applies to any problem where you distribute or consume from the tallest bars first.

2. Arithmetic series sum

The formula for summing consecutive integers from a down to b (inclusive): (a - b + 1) * (a + b) / 2. This building block appears in problems involving triangular numbers, range sums, and any scenario where you need the sum of a contiguous range of integers without iterating through them one by one.

def sum_range(high, low):
    count = high - low + 1
    return count * (high + low) // 2

Knowing this formula by heart lets you convert O(n) summation loops into O(1) calculations, which is exactly what makes the leveling approach fast enough for large inputs.

Edge cases

Before submitting, make sure your solution handles these:

• All colors have the same inventory [3, 3, 3], orders = 3: you sell one ball from each color at value 3. Profit = 9. The leveling happens in a single partial step.
• Single color inventory = [1000000000], orders = 1000000000: you sell every ball. The arithmetic series formula handles this in one step without iterating a billion times.
• Orders exactly fills one level: make sure you break out of the loop and do not accidentally try to level further.
• Large values and modular arithmetic: the intermediate products chunk * width can overflow 64-bit integers in some languages. In Python this is not an issue since integers have arbitrary precision, but in C++ or Java you need to be careful about where you apply the modulus.
• orders = 0: return 0 immediately. No balls sold, no profit.

From understanding to recall

You have read the greedy leveling solution and it makes sense. Sort, level, use the series formula, handle the partial row. But the implementation has many moving pieces: the width tracking, the arithmetic series with off-by-one concerns, the partial level with full_rows and leftover, and the modular arithmetic applied only to profit. These details are easy to mix up under pressure.

Spaced repetition closes that gap. You practice writing the leveling loop from scratch at increasing intervals. After a few rounds, the pattern is automatic. You see "maximize value from diminishing resources" and the code flows out without hesitation.

The greedy leveling pattern is one of roughly 60 reusable building blocks that cover hundreds of LeetCode problems. Learning them individually and drilling them with spaced repetition is far more effective than grinding random problems and hoping they stick.

Related posts

• Furthest Building You Can Reach - Another greedy problem where you allocate scarce resources optimally using a heap
• Kth Largest Element in an Array - Uses heap-based selection, the same tool you might reach for before discovering the leveling trick
• Task Scheduler - A greedy scheduling problem where you fill time slots from the most frequent tasks first

CodeBricks breaks the sell diminishing-valued colored balls problem into its greedy leveling and arithmetic series building blocks, then drills them independently with spaced repetition. You type each piece from scratch until the pattern is automatic. When a greedy optimization question shows up in your interview, you do not think about it. You just write it.