Python 1801.py
class Solution:
def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
result = 0
# basic order matching as done daily on every stock exchange worldwide
# (and I work at one ...)
bid = [] # max-heao, buy orders
ask = [] # min-heap, sell orders
# we could combine orders on same price level but it doesn't matter for this problem
for price, amount, type in orders:
# update heaps with new order
if type == 0:
heappush(bid, [ -price, amount ])
else:
heappush(ask, [ +price, amount ])
result += amount
# find crossed orders or orders on same price level
while bid and ask and -bid[0][0] >= ask[0][0]: # remember: bid is a max-heap
# match as much as possible
bidpx, bidsize = heappop(bid)
askpx, asksize = heappop(ask)
match = min(bidsize, asksize)
# re-insert non-yet-matched size
if bidsize > match:
heappush(bid, [ bidpx, bidsize - match ]) # price is already negative
if asksize > match:
heappush(ask, [ askpx, asksize - match ])
# matched on both sides of the orderbook
result -= 2 * match
return result % 1_000_000_007
Difficulty
and has an acceptance rate of about 54% (70k+ submissions).
Typical patterns to solve this problem:
- Array
- Heap (Priority Queue)
- Simulation
AI Disclaimer
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.
See this dedicated page for more details.
Code Walkthrough
Overview
The implementation processes a sequence of buy and sell orders and computes the total number of orders that remain unmatched after all possible trades have been executed. It maintains two priority queues-one for bids (buy orders) and one for asks (sell orders)-and continuously matches orders whenever the highest bid price meets or exceeds the lowest ask price. The final count is returned modulo 1 000 000 007.
Core Workflow
Initialization
The algorithm starts by creating an accumulator result set to zero. Two heaps are prepared: bid as a max-heap for buy orders and ask as a min-heap for sell orders.
result = 0
bid = [] # max-heap, stores [-price, amount]
ask = [] # min-heap, stores [price, amount]
Inserting New Orders
For each incoming order described by (price, amount, type), the code pushes the order onto the appropriate heap. A buy order (type == 0) is stored with a negated price so that the standard min-heap implementation behaves as a max-heap. A sell order (type == 1) is stored with its original price. The total result is increased by the order’s amount.
if type == 0:
heappush(bid, [-price, amount])
else:
heappush(ask, [price, amount])
result += amount
Matching Loop
After each insertion, the algorithm checks whether the top of the bid heap and the top of the ask heap represent a crossed market (-bid[0][0] >= ask[0][0]). While this condition holds, the highest-priced buy order and the lowest-priced sell order are popped, and the maximum possible quantity is traded (match = min(bidsize, asksize)). Any remaining quantity from either side is pushed back onto its heap. The accumulator result is decreased by twice the matched quantity because the matched units are removed from both sides of the order book.
while bid and ask and -bid[0][0] >= ask[0][0]:
bidpx, bidsize = heappop(bid)
askpx, asksize = heappop(ask)
match = min(bidsize, asksize)
if bidsize > match:
heappush(bid, [bidpx, bidsize - match])
if asksize > match:
heappush(ask, [askpx, asksize - match])
result -= 2 * match
Final Result
When all orders have been processed and no further matches are possible, the algorithm returns the remaining total modulo the required prime.
return result % 1_000_000_007
Edge Cases Handled
When a newly inserted order immediately matches an existing opposite-type order at the same price level, the while-loop executes at least once, ensuring that the trade is performed without leaving stale entries in the heaps.
If an order’s amount is larger than the counterpart’s amount, the excess portion is re-inserted into the appropriate heap with its original price, preserving the correct ordering for any subsequent matches.
When both heaps become empty after a series of matches, the condition bid and ask prevents further attempts to pop from an empty heap, safely terminating the matching loop.
The modulo operation is applied only at the final return, guaranteeing that intermediate arithmetic does not overflow the language’s integer limits while still delivering the required bounded result.
Performance Optimizations
The use of two binary heaps provides logarithmic time for each insertion and removal, which keeps the overall processing time proportional to the number of orders times the logarithm of the current heap size.
Storing the price as a negative value for the bid heap eliminates the need for a custom comparator, allowing the standard heapq implementation to be reused directly.
The algorithm maintains a single running total (result) that is updated incrementally as orders are added and matched, avoiding the need to recompute the sum of all remaining orders after each iteration.
By performing the modulo operation only once at the end, the code avoids repeated costly modulus calculations during the main loop, which can be significant when the number of orders is large.
The decision not to aggregate orders at identical price levels simplifies the data structure while still achieving correct results, because each individual order is processed in price order by the heap, and the matching logic correctly handles partial fills.
ELI5 - Simplified Explanation
Imagine you are at a playground where some children want to buy toys and others want to sell them. The buy orders are kept in a special pile where the ones who want to pay the most are on top, and the sell orders are in another pile where the ones who want the lowest price are on top.
When each new person arrives, they add their request to one of these piles. Then, the magic happens. The code looks at the very top of both piles to see if the person who wants to buy can afford the price the person wants to sell at. If the buyer has enough money, they make a deal.
When a deal is made, both the buyer and the seller take the toys or give the money, and they leave the playground. If one person wanted to trade more items than the other had, the person with the leftover items stays in the pile to wait for another match. This happens over and over until no more deals can be made. The final answer tells you how many toys are still waiting to be traded when the playground closes for the day.
Code Quality
Complexity Analysis
As a rule of thumb, the maximum input size for one second execution time is
- factorial: up to 10 elements
- exponential: up to 20 elements
- polynomial: a few thousand elements
- loglinear: up to 100,000 elements
- linear: a few million elements
- logarithmic: a billion elements
- constant: practically unlimited
Other Solutions
Obviously, I did that after I solved the problem myself.
In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.
And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.
(click on a column header to sort the table)
| author | ||||||||
|---|---|---|---|---|---|---|---|---|
| author | solutions | |||||||
| www | AlgoMonster | C++ | Java | Python | TS | |||
| WalkCCC | C++ | Java | ||||||
| leetcode.ca | C++ | Java | Go | Python | ||||
| Progiez | C++ | Java | Python | |||||
| github | black-shadows | C++ | ||||||
| charles-wangkai | Java | |||||||
| everthis | JS | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JS | |||||||
| suxrobGM | C# | |||||||
| wisdompeak | C++ | |||||||
| AlgoMonster | C++, Python, Java, TypeScript | |||||||
| WalkCCC | C++, Java | |||||||
| leetcode.ca | C++, Go, Java, Python | |||||||
| Progiez | C++, Java, Python | |||||||
| black-shadows | C++, C++ | |||||||
| charles-wangkai | Java | |||||||
| everthis | JavaScript | |||||||
| fsq | C++ | |||||||
| haoel | C++ | |||||||
| JoshCrozier | JavaScript | |||||||
| suxrobGM | C# | |||||||
| wisdompeak | C++ |
Videos
Solved On The Same Day
- problem 1827: Minimum Operations to Make the Array Increasing
- problem 1702: Maximum Binary String After Change
- problem 1547: Minimum Cost to Cut a Stick
- problem 1970: Last Day Where You Can Still Cross
Extra
- Tech Stack - my development environment and tools
- AI - how AI helped me create this website (NOT solving the problems)
- Progress - progression over time
- Quality - code quality