#1801

Medium

auto_awesomeArray plus Heap (Priority Queue)

LeetCode Problem Workspace

Number of Orders in the Backlog

Determine the total number of unfulfilled buy and sell orders using heaps to simulate backlog processing efficiently in order sequence.

array heap priority queue simulation

Problem Statement

You are given a 2D array orders where each element orders[i] = [pricei, amounti, orderTypei] represents amounti orders of type orderTypei at price pricei. orderTypei is 0 for buy orders and 1 for sell orders. All orders in orders[i] are processed before orders[i+1].

There is a backlog that starts empty. For each order, match it with the opposite type in the backlog: buy orders match the lowest-price sell orders and sell orders match the highest-price buy orders. Unmatched portions are added to the backlog. Return the total number of orders remaining in the backlog after processing all orders.

Examples

Example 1

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]

Output: 6

Here is what happens with the orders:

5 orders of type buy with price 10 are placed. There are no sell orders, so the 5 orders are added to the backlog.
2 orders of type sell with price 15 are placed. There are no buy orders with prices larger than or equal to 15, so the 2 orders are added to the backlog.
1 order of type sell with price 25 is placed. There are no buy orders with prices larger than or equal to 25 in the backlog, so this order is added to the backlog.
4 orders of type buy with price 30 are placed. The first 2 orders are matched with the 2 sell orders of the least price, which is 15 and these 2 sell orders are removed from the backlog. The 3rd order is matched with the sell order of the least price, which is 25 and this sell order is removed from the backlog. Then, there are no more sell orders in the backlog, so the 4th order is added to the backlog.

Finally, the backlog has 5 buy orders with price 10, and 1 buy order with price 30. So the total number of orders in the backlog is 6.

Example 2

Input: orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]

Output: 999999984

Here is what happens with the orders:

109 orders of type sell with price 7 are placed. There are no buy orders, so the 109 orders are added to the backlog.
3 orders of type buy with price 15 are placed. They are matched with the 3 sell orders with the least price which is 7, and those 3 sell orders are removed from the backlog.
999999995 orders of type buy with price 5 are placed. The least price of a sell order is 7, so the 999999995 orders are added to the backlog.
1 order of type sell with price 5 is placed. It is matched with the buy order of the highest price, which is 5, and that buy order is removed from the backlog.

Finally, the backlog has (1000000000-3) sell orders with price 7, and (999999995-1) buy orders with price 5. So the total number of orders = 1999999991, which is equal to 999999984 % (109 + 7).

Constraints

1 <= orders.length <= 105
orders[i].length == 3
1 <= pricei, amounti <= 109
orderTypei is either 0 or 1.

Solution Approach

Use Heaps to Track Backlog Orders

Maintain two heaps: a max heap for buy orders sorted by price and a min heap for sell orders sorted by price. This structure ensures that each incoming order can quickly find the best matching order in the backlog, which is key for efficient processing.

Greedy Matching per Order

Iterate through each order and attempt to match its quantity against the backlog using the heaps. Reduce quantities while matches exist, and only push remaining unmatched orders back into the appropriate heap. This ensures that each order is handled in order and avoids miscounting unfulfilled orders.

Compute Total Backlog

After processing all orders, sum the remaining amounts in both heaps. Use modulo operations if necessary to avoid overflow. This gives the total number of unexecuted orders, which directly answers the problem without extra traversal or sorting.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n log n) because each order may be pushed or popped from a heap at most once, and heap operations are log n. Space complexity is O(n) to store backlog orders in the heaps.

What Interviewers Usually Probe

Mentions using heaps to simulate the order backlog efficiently.
Asks about matching orders greedily by price.
Questions about handling large order quantities without overflow.

Common Pitfalls or Variants

Common pitfalls

Forgetting to process all batches in orders[i] when amounti > 1.
Mixing up max heap for buy orders and min heap for sell orders.
Incorrectly summing leftover orders leading to modulo mistakes.

Follow-up variants

Orders arriving in random order instead of sequentially by time.
Including additional order types beyond buy and sell.
Changing the matching rule to first-come-first-served instead of price priority.

FAQ

What data structures are optimal for the Number of Orders in the Backlog problem?

Two heaps are optimal: a max heap for buy orders and a min heap for sell orders, enabling efficient price-based matching.

Can we solve this problem without heaps?

Yes, but without heaps the solution may require full array scans for each order, increasing time complexity to O(n^2), which fails on large inputs.

How do I handle very large amounts in orders[i]?

Use modulo arithmetic to prevent integer overflow and ensure calculations stay within bounds.

Why do we match buy orders with lowest-price sell orders first?

Because the problem defines that buy orders execute with the cheapest available sell orders to minimize the price and simulate realistic trading.

What is the core pattern for this problem?

The pattern is Array plus Heap (Priority Queue), where arrays store the order sequence and heaps efficiently manage unfulfilled orders.

terminal

Solution

Solution 1: Priority Queue (Max-Min Heap) + Simulation

We can use a priority queue (max-min heap) to maintain the current backlog of orders, where the max heap `buy` maintains the backlog of purchase orders, and the min heap `sell` maintains the backlog of sales orders. Each element in the heap is a tuple $(price, amount)$, indicating that the number of orders at price `price` is `amount`.

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buy, sell = [], []
        for p, a, t in orders:
            if t == 0:
                while a and sell and sell[0][0] <= p:
                    x, y = heappop(sell)
                    if a >= y:
                        a -= y
                    else:
                        heappush(sell, (x, y - a))
                        a = 0
                if a:
                    heappush(buy, (-p, a))
            else:
                while a and buy and -buy[0][0] >= p:
                    x, y = heappop(buy)
                    if a >= y:
                        a -= y
                    else:
                        heappush(buy, (x, y - a))
                        a = 0
                if a:
                    heappush(sell, (p, a))
        mod = 10**9 + 7
        return sum(v[1] for v in buy + sell) % mod

Continue Practicing

#2357 make array zero by subtracting equal amounts #2402 meeting rooms iii #2462 total cost to hire k workers