Number of Orders in the Backlog: Dual Heap Simulation

You are given a 2D array orders where each entry is [price, amount, orderType]. Type 0 is a buy order and type 1 is a sell order. Process each order in sequence: try to match it against the opposite backlog, then add any remaining quantity to the appropriate backlog. Return the total number of orders remaining in both backlogs, modulo 10^9 + 7.

This is LeetCode 1801: Number of Orders in the Backlog, and it is a clean simulation problem that tests whether you can pick the right data structure. The answer is two heaps.

Why this problem matters

Order book matching is a real-world concept from financial exchanges. Every stock market runs a system that does exactly this: incoming buy orders get matched against the cheapest available sell orders, and incoming sell orders get matched against the most expensive available buy orders. This problem strips that idea down to its essentials.

From an interview perspective, this problem tests your ability to choose the right data structure for priority-based matching. If you reach for a sorted list or repeated linear scans, you will get a working solution that times out. Heaps give you O(log n) matching per order, which is what you need.

The key insight

Buy orders want to match with the cheapest sell orders. Sell orders want to match with the most expensive buy orders. That means you need quick access to:

• The highest price in the buy backlog (to check if a sell order can match)
• The lowest price in the sell backlog (to check if a buy order can match)

A max-heap for buys and a min-heap for sells gives you exactly that. The top of each heap is always the best candidate for matching.

The matching rule is simple: a buy order at price p can match any sell order with price <= p. A sell order at price p can match any buy order with price >= p. You keep matching until either the incoming order is fully filled or the opposite backlog has no more compatible orders.

The solution

import heapq

def get_number_of_backlog_orders(orders: list[list[int]]) -> int:
    MOD = 10**9 + 7
    buy = []
    sell = []

    for price, amount, order_type in orders:
        if order_type == 0:
            while amount > 0 and sell and sell[0][0] <= price:
                sell_price, sell_amount = heapq.heappop(sell)
                matched = min(amount, sell_amount)
                amount -= matched
                sell_amount -= matched
                if sell_amount > 0:
                    heapq.heappush(sell, (sell_price, sell_amount))
            if amount > 0:
                heapq.heappush(buy, (-price, amount))
        else:
            while amount > 0 and buy and -buy[0][0] >= price:
                buy_price_neg, buy_amount = heapq.heappop(buy)
                matched = min(amount, buy_amount)
                amount -= matched
                buy_amount -= matched
                if buy_amount > 0:
                    heapq.heappush(buy, (buy_price_neg, buy_amount))
            if amount > 0:
                heapq.heappush(sell, (price, amount))

    total = 0
    for _, amt in buy:
        total = (total + amt) % MOD
    for _, amt in sell:
        total = (total + amt) % MOD
    return total

Here is how the two heaps work together:

• Buy heap (max-heap): Python only has min-heaps, so we negate the price. The top of the heap is always the buy order willing to pay the most. When a sell order comes in, we check if -buy[0][0] (the highest buy price) is at least the sell price.
• Sell heap (min-heap): The top of the heap is always the cheapest sell order. When a buy order comes in, we check if sell[0][0] (the lowest sell price) is at most the buy price.
• Matching loop: For each incoming order, keep popping from the opposite heap and filling as many units as possible. If a partially filled order remains on the heap side, push the remainder back. If the incoming order still has leftover amount, push it onto its own heap.

Visual walkthrough

Let's trace through orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]] step by step.

Complexity analysis

Time: O(n log n). Each order involves at most O(log n) heap operations. In the worst case, every order gets pushed and later popped, giving O(n) heap operations total, each costing O(log n).

Space: O(n). In the worst case, every order ends up in the backlog (no matches at all), so both heaps together hold n entries.

The building blocks

1. Max-heap / min-heap pair

The core pattern here is using two heaps to maintain two-sided priority access. You see this in problems where you need the maximum from one set and the minimum from another. The classic example is the "Find Median from Data Stream" problem, where a max-heap holds the lower half and a min-heap holds the upper half. Here, the buy backlog is a max-heap and the sell backlog is a min-heap.

The template for a max-heap in Python using negation:

import heapq

max_heap = []
heapq.heappush(max_heap, -value)
top = -max_heap[0]

2. Greedy matching with heaps

When you need to match items greedily by priority, a heap lets you always grab the best candidate in O(log n). The pattern is: pop the top, consume as much as you can, push back any remainder. This shows up in scheduling problems, resource allocation, and anywhere you process items in priority order.

while amount > 0 and heap and heap[0] meets_condition:
    best = heapq.heappop(heap)
    used = min(amount, best.quantity)
    amount -= used
    if best.quantity - used > 0:
        heapq.heappush(heap, updated_best)

Edge cases

• No matches at all. Every buy price is below every sell price. All orders accumulate in their respective heaps untouched. The answer is the sum of all amounts.
• All orders fully matched. If buy and sell prices overlap perfectly and amounts cancel out, both heaps end up empty. The answer is 0.
• Single order. One buy or one sell with nothing to match. It sits in the backlog. The answer is its amount.
• Large amounts. Amounts can be up to 10^9, so the total can overflow 32-bit integers. The mod operation handles this, but make sure you apply it at the end when summing.
• Partial fills. An incoming order might match multiple entries from the opposite heap. The while loop handles this naturally by continuing to pop and match until the order is filled or the heap runs dry.

From understanding to recall

The logic here is not tricky once you see the two-heap structure. The part you might forget under pressure is the matching loop mechanics: when to pop, when to push back the remainder, and the negation trick for the max-heap.

The fix is to practice the matching loop in isolation. Write the "pop, match, push remainder" pattern a few times and it becomes automatic. The heap operations are the same every time. What changes between problems is just the matching condition (here it is price comparison, elsewhere it might be time or capacity).

Spaced repetition locks in the loop structure so you do not have to rethink it each time. After a few reps, "check top of opposite heap, pop, match, push back" becomes muscle memory.

Related posts

• Kth Largest Element in an Array - Another heap problem where choosing the right heap type (min vs max) is the key decision
• Task Scheduler - Uses frequency-based greedy logic with heaps for scheduling, a different angle on priority-based processing
• Top K Frequent Elements - Demonstrates the min-heap-of-size-k pattern for selecting top elements by priority

---

Understanding order matching gives you a template for any problem where two competing sides need to be reconciled by priority. The dual heap pattern is the tool that makes it efficient.