0385MediumArrayMathBinary SearchGreedySortingHeap (Priority Queue)

Rare Poster Revenue

Tracked in this browser only

Trains the technique from

LeetCode 1648Sell Diminishing-Valued Colored Balls

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

A poster archive prices reprints by scarcity. stacks[i] is how many copies of design i are left in the drawer, and a copy of a design that still has k copies in the drawer sells for exactly k credits, after which that design has k - 1 copies left.

A wholesaler has paid for orders copies in total and does not care which designs they come from, so you choose the design each copy is drawn from, one copy at a time.

Return the largest total number of credits the archive can take in, modulo 10^9 + 7.

Examples

Example 1

Input: stacks = [2, 5], orders = 4
Output: 14

Draw from design 1 at 5, 4 and 3 credits, then from design 0 at 2 credits, for 14 credits in total.

Example 2

Input: stacks = [3, 5], orders = 6
Output: 19

Draw from design 1 at 5 and 4 credits, then from design 0 at 3 credits, then design 1 at 3, then design 0 at 2, then design 1 at 2, for 19 credits.

Example 3

Input: stacks = [4, 4, 4], orders = 5
Output: 18

Draw one copy of each design at 4 credits, then two more copies at 3 credits each, for 18 credits.

Example 4

Input: stacks = [7], orders = 7
Output: 28

Only one design exists, so its copies go at 7, 6, 5, 4, 3, 2 and 1 credits.

Constraints

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

The signature

The editor is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def max_profit(stacks: list[int], orders: int) -> int:

Java

public int maxProfit(int[] stacks, int orders)

The intended approach

Time O(n log n)Space O(n) for the sorted copy

Sort the drawer counts from largest to smallest and level the tallest designs downwards one tier at a time. After the first `i + 1` designs have been levelled to the height of the next distinct count, all `i + 1` of them sell copies at the same prices, so the credits for dropping them from `top` down to `floor + 1` is an arithmetic series and needs no per-copy loop. When the remaining orders cannot pay for a whole tier, take as many complete rows as they cover and hand the leftover copies out at the next price down.

Pythonentry point: max_profit

def max_profit(stacks, orders):
    # Time O(n log n) for the sort; the walk over tiers is O(n).
    # Space O(n) for the sorted copy.
    MOD = 10 ** 9 + 7
    tiers = sorted(stacks, reverse=True)
    tiers.append(0)
    total = 0
    left = orders
    i = 0
    while left > 0 and i + 1 < len(tiers):
        width = i + 1
        top = tiers[i]
        floor = tiers[i + 1]
        drop = top - floor
        block = drop * width
        if block <= left:
            total += width * (top + floor + 1) * drop // 2
            left -= block
        else:
            full = left // width
            total += width * (top + top - full + 1) * full // 2
            rest = left % width
            total += rest * (top - full)
            left = 0
        i += 1
    return total % MOD

The obvious version

Keep the drawer counts in a max-heap and sell one copy at a time, pushing the decremented count back each time. Linear in `orders`, which is far too slow at the stated bounds but obviously correct.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_max_profit(stacks, orders):
    import heapq
    heap = [-count for count in stacks]
    heapq.heapify(heap)
    total = 0
    left = orders
    while left > 0:
        top = -heapq.heappop(heap)
        total += top
        if top > 1:
            heapq.heappush(heap, -(top - 1))
        left -= 1
    return total % (10 ** 9 + 7)

How this problem was checked

Reference solution executed against 9 test cases — 9 passed
4 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in