LeetCode 1801 - Number of Orders in the Backlog

LeetCode Problem 1801

Difficulty: 🟡 Medium
Topics: Array, Heap (Priority Queue), Simulation

Solution

Problem Understanding

This problem simulates a simplified stock exchange order book. Each incoming order is either a buy order or a sell order, and each order contains a price and an amount. Orders are processed strictly in the order they appear in the input.

A buy order wants to purchase shares at a certain maximum price. A sell order wants to sell shares at a certain minimum price. Matching occurs whenever a buy order can afford the cheapest sell order currently available, or when a sell order can be satisfied by the most expensive buy order currently available.

The key detail is that matching always happens against the best available price:

• Buy orders match against the sell order with the smallest price.
• Sell orders match against the buy order with the largest price.

If a match is possible, orders are executed immediately. Partial matching is allowed, meaning only part of an order may be consumed during a transaction. Any remaining unmatched amount stays in the backlog.

The input orders[i] = [pricei, amounti, orderTypei] means:

• pricei is the order price

• amounti is how many units are being bought or sold

• orderTypei is:

• 0 for buy

• 1 for sell

The goal is to process every order and return the total number of remaining units in the backlog after all possible matching has been completed.

The constraints are very important:

• Up to 10^5 orders
• Prices and amounts can be as large as 10^9

A naive simulation that scans all existing orders for every new order would be far too slow. Since we repeatedly need:

• the smallest sell price
• the largest buy price

this strongly suggests using priority queues, also known as heaps.

Some important edge cases include:

• Orders that match only partially
• Orders that completely consume multiple backlog entries
• Situations where no match is possible
• Very large amounts requiring modulo arithmetic
• Many orders with the same price
• Cases where one backlog heap becomes empty during matching

The problem guarantees valid input formatting and valid order types, so we only need to focus on correct matching behavior and efficiency.

Approaches

Brute Force Approach

A straightforward solution would maintain two lists:

• all pending buy orders
• all pending sell orders

For every incoming order, we would scan the opposite list to find the best possible matching order:

• smallest sell price for a buy order
• largest buy price for a sell order

After finding a candidate, we would update quantities and continue matching until no valid trade remains.

This approach is correct because it faithfully simulates the exchange process exactly as described. However, it is inefficient because every insertion may require scanning many existing orders.

In the worst case:

• each of the 10^5 orders scans nearly all previous orders
• total complexity becomes O(n^2)

That is too slow for the given constraints.

Optimal Approach Using Two Heaps

The critical observation is that we only ever care about:

• the minimum sell price
• the maximum buy price

Priority queues are ideal for this:

• a min heap for sell orders
• a max heap for buy orders

With heaps:

• retrieving the best matching order becomes O(log n)
• insertion also becomes O(log n)

Python only provides a min heap, so for buy orders we store negative prices to simulate a max heap.

The algorithm repeatedly matches orders against the top of the opposite heap until:

• the current order is fully consumed, or
• no valid price match exists

This reduces the total complexity to O(n log n).

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Scans backlog lists repeatedly
Optimal	O(n log n)	O(n)	Uses two heaps for efficient matching

Algorithm Walkthrough

1. Initialize two heaps.

We maintain:

• a max heap for buy orders
• a min heap for sell orders

Each heap entry stores:

• price
• remaining amount

The buy heap uses negative prices because Python heaps are min heaps by default. 2. Process each order in sequence.

Every order must be handled in the exact order given by the input. 3. Handle a buy order.

For a buy order:

• repeatedly check the cheapest sell order
• if the sell price is less than or equal to the buy price, a trade can happen

During each match:

• compute the matched quantity
• reduce both amounts
• remove fully consumed sell orders from the heap

Continue until:

• the buy order is fully satisfied, or
• no affordable sell order exists

4. Add remaining buy quantity to the backlog.

If part of the buy order remains unmatched, insert it into the buy heap. 5. Handle a sell order.

For a sell order:

• repeatedly check the highest buy price
• if the buy price is greater than or equal to the sell price, a trade can happen

During each match:

• compute the matched quantity
• reduce both amounts
• remove fully consumed buy orders

Continue until:

• the sell order is fully consumed, or
• no matching buy order exists

6. Add remaining sell quantity to the backlog.

If some sell quantity remains unmatched, push it into the sell heap. 7. Compute the final backlog size.

Sum all remaining amounts from:

• buy heap
• sell heap

Return the result modulo 10^9 + 7.

Why it works

The heaps always maintain the correct priority order:

• the buy heap always exposes the highest buy price
• the sell heap always exposes the lowest sell price

At every step, the algorithm performs exactly the same trades the problem statement requires. Since orders are processed sequentially and matching continues greedily while valid prices exist, the final backlog state is identical to the intended exchange simulation.

Python Solution

from typing import List
import heapq

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        MOD = 10**9 + 7

        # Max heap for buy orders: (-price, amount)
        buy_heap = []

        # Min heap for sell orders: (price, amount)
        sell_heap = []

        for price, amount, order_type in orders:

            # Buy order
            if order_type == 0:

                # Match with cheapest sell orders
                while amount > 0 and sell_heap and sell_heap[0][0] <= price:
                    sell_price, sell_amount = heapq.heappop(sell_heap)

                    matched = min(amount, sell_amount)

                    amount -= matched
                    sell_amount -= matched

                    # Put remaining sell order back
                    if sell_amount > 0:
                        heapq.heappush(sell_heap, (sell_price, sell_amount))

                # Remaining buy order goes to backlog
                if amount > 0:
                    heapq.heappush(buy_heap, (-price, amount))

            # Sell order
            else:

                # Match with highest buy orders
                while amount > 0 and buy_heap and -buy_heap[0][0] >= price:
                    buy_price, buy_amount = heapq.heappop(buy_heap)

                    matched = min(amount, buy_amount)

                    amount -= matched
                    buy_amount -= matched

                    # Put remaining buy order back
                    if buy_amount > 0:
                        heapq.heappush(buy_heap, (buy_price, buy_amount))

                # Remaining sell order goes to backlog
                if amount > 0:
                    heapq.heappush(sell_heap, (price, amount))

        total = 0

        for _, amount in buy_heap:
            total = (total + amount) % MOD

        for _, amount in sell_heap:
            total = (total + amount) % MOD

        return total

The implementation directly follows the heap-based simulation strategy.

The buy_heap stores negative prices so that the smallest value in the heap corresponds to the largest actual buy price. This allows efficient access to the best available buy order.

The sell_heap naturally works as a min heap because we always need the smallest sell price.

For each order, the code repeatedly attempts matching against the opposite heap. The matching continues until either:

• the current order has no remaining quantity
• the price condition fails
• the opposite heap becomes empty

Partial matching is handled carefully. After a trade, if the backlog order still has remaining quantity, it is pushed back into the heap with its updated amount.

Finally, all remaining quantities in both heaps are summed modulo 10^9 + 7.

Go Solution

package main

import (
	"container/heap"
)

const MOD int = 1e9 + 7

type Order struct {
	price  int
	amount int
}

type BuyHeap []Order

func (h BuyHeap) Len() int {
	return len(h)
}

func (h BuyHeap) Less(i, j int) bool {
	return h[i].price > h[j].price
}

func (h BuyHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *BuyHeap) Push(x interface{}) {
	*h = append(*h, x.(Order))
}

func (h *BuyHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

type SellHeap []Order

func (h SellHeap) Len() int {
	return len(h)
}

func (h SellHeap) Less(i, j int) bool {
	return h[i].price < h[j].price
}

func (h SellHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *SellHeap) Push(x interface{}) {
	*h = append(*h, x.(Order))
}

func (h *SellHeap) Pop() interface{} {
	old := *h
	n := len(old)
	item := old[n-1]
	*h = old[:n-1]
	return item
}

func getNumberOfBacklogOrders(orders [][]int) int {
	buyHeap := &BuyHeap{}
	sellHeap := &SellHeap{}

	heap.Init(buyHeap)
	heap.Init(sellHeap)

	for _, order := range orders {
		price := order[0]
		amount := order[1]
		orderType := order[2]

		if orderType == 0 {

			for amount > 0 &&
				sellHeap.Len() > 0 &&
				(*sellHeap)[0].price <= price {

				top := heap.Pop(sellHeap).(Order)

				matched := min(amount, top.amount)

				amount -= matched
				top.amount -= matched

				if top.amount > 0 {
					heap.Push(sellHeap, top)
				}
			}

			if amount > 0 {
				heap.Push(buyHeap, Order{
					price:  price,
					amount: amount,
				})
			}

		} else {

			for amount > 0 &&
				buyHeap.Len() > 0 &&
				(*buyHeap)[0].price >= price {

				top := heap.Pop(buyHeap).(Order)

				matched := min(amount, top.amount)

				amount -= matched
				top.amount -= matched

				if top.amount > 0 {
					heap.Push(buyHeap, top)
				}
			}

			if amount > 0 {
				heap.Push(sellHeap, Order{
					price:  price,
					amount: amount,
				})
			}
		}
	}

	total := 0

	for buyHeap.Len() > 0 {
		order := heap.Pop(buyHeap).(Order)
		total = (total + order.amount) % MOD
	}

	for sellHeap.Len() > 0 {
		order := heap.Pop(sellHeap).(Order)
		total = (total + order.amount) % MOD
	}

	return total
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

The Go version uses the container/heap package, which requires implementing the heap interface manually.

Unlike Python, Go does not need negative prices for the buy heap because we can customize the Less function directly. The buy heap therefore behaves as a max heap naturally.

The logic for matching and reinserting partially consumed orders is identical to the Python solution.

Worked Examples

Example 1

Input:

[[10,5,0],[15,2,1],[25,1,1],[30,4,0]]

Step	Current Order	Buy Heap	Sell Heap	Action
1	Buy 5 @ 10	[(10,5)]	[]	No sell orders
2	Sell 2 @ 15	[(10,5)]	[(15,2)]	Buy price too small
3	Sell 1 @ 25	[(10,5)]	[(15,2),(25,1)]	Buy price too small
4	Buy 4 @ 30	[(10,5)]	[(15,2),(25,1)]	Start matching

Now process the final buy order:

• Match 2 units with sell @ 15
• Remaining buy amount = 2

Sell heap becomes:

[(25,1)]

Next match:

• Match 1 unit with sell @ 25
• Remaining buy amount = 1

Sell heap becomes empty.

Remaining buy order:

(30,1)

Final heaps:

Buy heap:

[(30,1),(10,5)]

Sell heap:

[]

Total backlog:

1 + 5 = 6

Example 2

Input:

[[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]

Step	Current Order	Buy Heap	Sell Heap	Action
1	Sell 1e9 @ 7	[]	[(7,1e9)]	No buy orders
2	Buy 3 @ 15	[]	[(7,999999997)]	Match 3
3	Buy 999999995 @ 5	[(5,999999995)]	[(7,999999997)]	Cannot match
4	Sell 1 @ 5	[(5,999999994)]	[(7,999999997)]	Match 1

Final backlog:

999999997 + 999999994
= 1999999991

Modulo result:

1999999991 % (10^9 + 7)
= 999999984

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each order is inserted and removed from heaps at most once
Space	O(n)	In the worst case, all orders remain in the backlog

The time complexity comes from heap operations. Every push and pop operation costs O(log n). Since each order enters and leaves a heap at most once, the total number of heap operations is linear in the number of orders.

The space complexity is O(n) because all orders could remain unmatched and therefore stay in the heaps.

Test Cases

from typing import List

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        import heapq

        MOD = 10**9 + 7

        buy_heap = []
        sell_heap = []

        for price, amount, order_type in orders:

            if order_type == 0:

                while amount > 0 and sell_heap and sell_heap[0][0] <= price:
                    sell_price, sell_amount = heapq.heappop(sell_heap)

                    matched = min(amount, sell_amount)

                    amount -= matched
                    sell_amount -= matched

                    if sell_amount > 0:
                        heapq.heappush(sell_heap, (sell_price, sell_amount))

                if amount > 0:
                    heapq.heappush(buy_heap, (-price, amount))

            else:

                while amount > 0 and buy_heap and -buy_heap[0][0] >= price:
                    buy_price, buy_amount = heapq.heappop(buy_heap)

                    matched = min(amount, buy_amount)

                    amount -= matched
                    buy_amount -= matched

                    if buy_amount > 0:
                        heapq.heappush(buy_heap, (buy_price, buy_amount))

                if amount > 0:
                    heapq.heappush(sell_heap, (price, amount))

        total = 0

        for _, amount in buy_heap:
            total = (total + amount) % MOD

        for _, amount in sell_heap:
            total = (total + amount) % MOD

        return total

sol = Solution()

# Provided example 1
assert sol.getNumberOfBacklogOrders(
    [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
) == 6

# Provided example 2
assert sol.getNumberOfBacklogOrders(
    [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
) == 999999984

# Exact full matching
assert sol.getNumberOfBacklogOrders(
    [[10,5,0],[10,5,1]]
) == 0

# Partial matching with remaining buy order
assert sol.getNumberOfBacklogOrders(
    [[10,10,0],[5,4,1]]
) == 6

# Partial matching with remaining sell order
assert sol.getNumberOfBacklogOrders(
    [[10,4,0],[5,10,1]]
) == 6

# No matches possible
assert sol.getNumberOfBacklogOrders(
    [[5,10,0],[10,10,1]]
) == 20

# Multiple cascading matches
assert sol.getNumberOfBacklogOrders(
    [[20,5,0],[15,3,1],[10,2,1]]
) == 0

# Multiple orders with same price
assert sol.getNumberOfBacklogOrders(
    [[10,5,0],[10,3,0],[10,6,1]]
) == 2

# Single order only
assert sol.getNumberOfBacklogOrders(
    [[100,1,0]]
) == 1

# Large values stress test
assert sol.getNumberOfBacklogOrders(
    [[1,10**9,0]]
) == 1000000000 % (10**9 + 7)

print("All tests passed!")

Test	Why
Example 1	Validates standard matching behavior
Example 2	Validates modulo arithmetic and huge amounts
Exact full matching	Ensures complete cancellation works
Remaining buy order	Tests partial consumption of sell orders
Remaining sell order	Tests partial consumption of buy orders
No matches possible	Ensures orders stay in backlog correctly
Cascading matches	Validates repeated heap matching
Same price orders	Ensures equal-price matching works
Single order	Smallest meaningful input
Large values	Verifies handling of huge quantities

Edge Cases

Partial Order Consumption

One of the most common sources of bugs is partial matching. For example, a buy order may consume only part of a sell order. The remaining portion must stay in the backlog with the same price.

The implementation handles this by:

1. removing the top heap order
2. reducing its amount
3. pushing it back into the heap if quantity remains

This guarantees no leftover quantity is lost.

Multiple Consecutive Matches

An incoming order may need to match against many backlog entries. For example, one large buy order might consume several sell orders in ascending price order.

A single if statement would fail here because only one trade would occur. The implementation correctly uses a while loop so matching continues until no valid trade remains.

Extremely Large Amounts

Amounts may be as large as 10^9, and many such orders can accumulate. The total backlog size can exceed normal integer ranges in some languages.

The solution avoids overflow issues by:

• using Python integers, which automatically expand
• using modulo arithmetic during the final sum
• relying on Go's 64-bit integer behavior being sufficient for the constraints

This ensures correct results even for the largest inputs allowed by the problem.