Problem 1801

Abstract / Summary

Count how many orders are still waiting to be processed based on given arrival and processing times.

Note

The full problem description, including helpful examples, can be found on LeetCode.

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
35 lines | 1433 bytes | submitted January 21, 2024 | GitHub   57% comment ratio | tab size 4 | low complexity

Difficulty

This problem is ranked as
easy medium hard

and has an acceptance rate of about 54% (70k+ submissions).

Typical patterns to solve this problem:
  • Array
  • Heap (Priority Queue)
  • Simulation
I solved 663 easy, 1250 medium and 309 hard problems

AI Disclaimer

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
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.
LeetCode profile | GitHub repo

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.

written by openai gpt

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.

written by google gemini

Code Quality

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):
n = 27 | median = 7 | μ = 7.19 | σ = 1.22

Complexity Analysis

Time: loglinear
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
generated automatically

Other Solutions

I wrote a basic crawler to find other solutions to that problem.
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++
21 links | 12 authors | 7 languages

Videos

4 videos   did my crawler come up with invalid videos ? drop me a line.

Solved On The Same Day

5 solutions   January 21, 2024

Extra

There are a few extra pages giving you some insights into my setup:
  • 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