0886MediumArrayHeap (Priority Queue)Simulation

Lots Left on the Produce Book

Tracked in this browser only

Trains the technique from

LeetCode 1801Number of Orders in the Backlog

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 produce desk works through instructions in the order logged. Each entry of orders is [price, lots, kind], where kind is 0 for a buy and 1 for a sell.

A buy is filled lot by lot against the cheapest sell waiting on the book, so long as that sell's price is at most the buy's price. A sell is filled against the dearest buy waiting, so long as that buy's price is at least the sell's price. Filling removes lots from both sides, and a waiting order leaves the book once all its lots are gone. Whatever cannot be filled joins the book itself.

Return the total lots left on the book once every instruction has been worked through, modulo 10^9 + 7.

Examples

Example 1

Input: orders = [[23, 5, 0], [19, 4, 1], [26, 3, 1], [21, 7, 0]]
Output: 11

The buy at 23 goes on the book first. The sell at 19 fills 4 of its lots, leaving 1 buy lot at 23. The sell at 26 finds no buy dear enough and joins the book. The buy at 21 finds the cheapest sell priced 26, which is too dear, so its 7 lots join too, leaving 1 plus 3 plus 7 lots waiting.

Example 2

Input: orders = [[10, 5, 0], [11, 5, 1]]
Output: 10

The sell wants 11 a lot and the only buy offers 10, so nothing fills and all ten lots stay on the book.

Example 3

Input: orders = [[10, 5, 0], [10, 5, 1]]
Output: 0

An equal price is good enough to fill, so the two orders clear each other out.

Constraints

1 <= orders.length <= 10^5
orders[i].length == 3
1 <= orders[i][0] <= 10^9
1 <= orders[i][1] <= 10^9
orders[i][2] is either 0 or 1

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 get_number_of_backlog_orders(orders: list[list[int]]) -> int:

Java

public int getNumberOfBacklogOrders(int[][] orders)

The intended approach

Time O(n log n) for n instructions: each one does a bounded number of heap pushes plus the pops that retire an order for good.Space O(n) for the two heaps.

Each instruction only ever needs one thing from the book: the cheapest waiting sell, or the dearest waiting buy. Nothing else about the book is consulted, so hold the sells in a heap ordered smallest price first and the buys in a heap ordered largest price first. Working an instruction then means repeatedly looking at the top of the opposite heap and filling against it while the price still works and lots remain, taking off the smaller of the two lot counts each time. An order at the top that runs out is popped; an order that survives keeps its reduced lot count. Whatever lots are still unfilled when the price no longer works go onto the order's own heap. Every heap entry is pushed once and popped once, so the total work stays near linear.

Pythonentry point: get_number_of_backlog_orders

def get_number_of_backlog_orders(orders):
    import heapq
    sells = []   # smallest price first
    buys = []    # largest price first, so prices are negated
    for price, lots, kind in orders:
        if kind == 0:
            while lots > 0 and sells and sells[0][0] <= price:
                best_price, best_lots = sells[0]
                take = best_lots if best_lots < lots else lots
                lots -= take
                best_lots -= take
                if best_lots == 0:
                    heapq.heappop(sells)
                else:
                    sells[0] = (best_price, best_lots)
            if lots > 0:
                heapq.heappush(buys, (-price, lots))
        else:
            while lots > 0 and buys and -buys[0][0] >= price:
                best_price, best_lots = buys[0]
                take = best_lots if best_lots < lots else lots
                lots -= take
                best_lots -= take
                if best_lots == 0:
                    heapq.heappop(buys)
                else:
                    buys[0] = (best_price, best_lots)
            if lots > 0:
                heapq.heappush(sells, (price, lots))
    total = 0
    for _p, lots in sells:
        total += lots
    for _p, lots in buys:
        total += lots
    return total % 1000000007

The obvious version

Hold the book as two plain lists and, for every instruction, scan the whole opposite list from the start to find the best price on offer. Quadratic in the instruction count, but it never relies on the book being kept in any order.

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_get_number_of_backlog_orders(orders):
    sells = []
    buys = []
    for price, lots, kind in orders:
        if kind == 0:
            while lots > 0 and sells:
                at = 0
                for i in range(1, len(sells)):
                    if sells[i][0] < sells[at][0]:
                        at = i
                if sells[at][0] > price:
                    break
                take = sells[at][1] if sells[at][1] < lots else lots
                lots -= take
                sells[at] = [sells[at][0], sells[at][1] - take]
                if sells[at][1] == 0:
                    sells.pop(at)
            if lots > 0:
                buys.append([price, lots])
        else:
            while lots > 0 and buys:
                at = 0
                for i in range(1, len(buys)):
                    if buys[i][0] > buys[at][0]:
                        at = i
                if buys[at][0] < price:
                    break
                take = buys[at][1] if buys[at][1] < lots else lots
                lots -= take
                buys[at] = [buys[at][0], buys[at][1] - take]
                if buys[at][1] == 0:
                    buys.pop(at)
            if lots > 0:
                sells.append([price, lots])
    total = 0
    for entry in sells:
        total += entry[1]
    for entry in buys:
        total += entry[1]
    return total % 1000000007

How this problem was checked

Reference solution executed against 12 test cases — 12 passed
3 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