The next lot to beat it

At a fish market the lots go under the hammer one after another, and a buyer wants to know which later lot first beat the ones she followed.

The problem

The auctioneer's sheet lists the hammer price of every lot in the order it was sold, and no two lots fetched the same price. The buyer kept her own short list — a subset of that sheet, in her own order — and for each entry she wants the price of the first lot sold after it that fetched more, or -1 if none did.

"After" means later in the sale, not larger in value: she wants the nearest lot that beat the price, not the best price of the rest of the day.

Input. hammer — the hammer prices in sale order, all distinct. watched — prices, each one appearing somewhere in hammer.

Output. A list the length of watched, holding those answers in order.

Example.

hammer = [42, 17, 65, 23, 51], watched = [17, 65, 51]  ->  [65, -1, -1]

Lot 17 is beaten by the next lot, 65. Lot 65 is never beaten — 23 and 51 both fall short — and lot 51 is last, so nothing follows it.

A second example, where the nearest winner and the biggest later lot differ:

hammer = [30, 12, 14, 28, 9, 60], watched = [12, 28, 9, 30]  ->  [14, 60, 60, 60]

Lot 12 is answered by 14, the very next lot, even though 60 comes later and is far larger. Lot 28 waits until the end of the sale, and so does 30, the first lot of the day.

Constraints.

• 1 <= len(hammer) <= 10^5
• 1 <= len(watched) <= len(hammer)
• 1 <= hammer[i] <= 10^9, all distinct
• every value in watched appears in hammer

Hints

Approach

Brute force

For each watched price, find it on the sheet and walk right until a bigger price appears: O(len(watched) · len(hammer)) comparisons, about 10^10 at the bounds. A sale that only falls in price makes every one of those scans run to the end.

The insight

Scanning the sale from the last lot backwards, any lot that is smaller than the one you are standing on can be discarded forever — the current lot is both larger and closer for everything still to the left.

That is what makes a stack legal here: a discarded lot is dominated on both counts a query cares about, price and proximity. So the lots worth remembering increase from the current position rightwards, and the first one above the current price is the stack top once the smaller ones are popped off. Each lot is pushed once and popped once.

Algorithm

1. Start with an empty stack and an empty map from price to answer.
2. Walk hammer from the last lot to the first, taking each price.
3. Pop while the stack top is less than price — those lots can never answer anything further left.
4. Record answer[price] as the stack top, or -1 if the stack is empty.
5. Push price.
6. Read the map once per entry in watched.

Complexity

Time O(n + m) for n lots and m watched entries — every lot is pushed once and popped at most once, each lookup O(1). Space O(n) for the map, plus a stack that holds the whole sheet when prices only fall.

Solution

"""The next lot to beat it — one right-to-left pass with a monotonic stack."""


def solve(hammer, watched):
    # Stack invariant: read bottom to top, the prices on it strictly decrease.
    # Each one beats every lot sold after it, so nothing between the current lot
    # and the stack top could have answered first.
    unbeaten = []
    beaten_by = {}

    for price in reversed(hammer):
        while unbeaten and unbeaten[-1] < price:
            unbeaten.pop()          # sold later and for less: dominated, never an answer
        beaten_by[price] = unbeaten[-1] if unbeaten else -1
        unbeaten.append(price)

    return [beaten_by[price] for price in watched]

TESTS = [
    (([42, 17, 65, 23, 51], [17, 65, 51]), [65, -1, -1]),
    (([30, 12, 14, 28, 9, 60], [12, 28, 9, 30]), [14, 60, 60, 60]),
    # A single lot has nothing after it.
    (([88], [88]), [-1]),
    # A sale that only falls: the stack grows to the whole sheet and no lot is beaten.
    (([9, 7, 5, 3], [9, 7, 5, 3]), [-1, -1, -1, -1]),
    # A sale that only rises: every lot is answered by its immediate successor.
    (([3, 5, 7, 9], [3, 5, 7, 9]), [5, 7, 9, -1]),
    # The nearest beater is not the last lot of the day.
    (([50, 10, 20, 40, 30], [10, 40, 20]), [20, -1, 40]),
]

Pitfalls

• Pushing the current price before reading the top. The top is then the lot itself, and every answer comes back equal to its own price.
• Answering with the largest later price instead of the first one above it. On [30, 12, 14, 28, 9, 60] lot 12's answer becomes 60, when the very next lot, 14, already beat it.
• Forgetting the empty stack. The dearest lot of the day, and the last lot whatever it fetched, have nothing above them; reading stack[-1] there raises an IndexError instead of answering -1.

Variants

• Waiting for a stronger gust — the same stack storing positions, answering with a distance not a value.
• Stacks and monotonic stacks — the lesson deriving this pattern from the double loop.