# Number of Orders in the Backlog
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/number-of-orders-in-the-backlog)
Canonical: https://scaleengineer.com/dsa/problems/number-of-orders-in-the-backlog
**Data structures:** Array, Heap (Priority Queue)
**Companies:** [Jane Street](https://scaleengineer.com/companies/jane-street), [Coinbase](https://scaleengineer.com/companies/coinbase), [Robinhood](https://scaleengineer.com/companies/robinhood)
---
## Problem
You are given a 2D integer array `orders`, where each `orders[i] = [pricei, amounti, orderTypei]` denotes that `amounti` orders have been placed of type `orderTypei` at the price `pricei`. The `orderTypei` is:

* `0` if it is a batch of `buy` orders, or
* `1` if it is a batch of `sell` orders.

Note that `orders[i]` represents a batch of `amounti` independent orders with the same price and order type. All orders represented by `orders[i]` will be placed before all orders represented by `orders[i+1]` for all valid `i`.

There is a **backlog** that consists of orders that have not been executed. The backlog is initially empty. When an order is placed, the following happens:

* If the order is a `buy` order, you look at the `sell` order with the **smallest** price in the backlog. If that `sell` order's price is **smaller than or equal to** the current `buy` order's price, they will match and be executed, and that `sell` order will be removed from the backlog. Else, the `buy` order is added to the backlog.
* Vice versa, if the order is a `sell` order, you look at the `buy` order with the **largest** price in the backlog. If that `buy` order's price is **larger than or equal to** the current `sell` order's price, they will match and be executed, and that `buy` order will be removed from the backlog. Else, the `sell` order is added to the backlog.

Return _the total **amount** of orders in the backlog after placing all the orders from the input_. Since this number can be large, return it **modulo** `109 + 7`.

**Example 1:**

![](https://assets.glich.co/dsa/number-of-orders-in-the-backlog/image0.png) 

**Input:** orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
**Output:** 6
**Explanation:** 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:**

![](https://assets.glich.co/dsa/number-of-orders-in-the-backlog/image1.png) 

**Input:** orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
**Output:** 999999984
**Explanation:** 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`.

# Approaches
## Brute Force Simulation with Lists
This approach directly simulates the process described in the problem using two simple lists to represent the buy and sell backlogs. For each incoming order, it linearly scans the corresponding opposite backlog to find a suitable match. While straightforward to understand, this method is highly inefficient.
**Time:** O(N^3), where N is the number of orders. For each of the N orders, we might need to match it against multiple orders in the backlog. Each match requires a linear scan (O(K)) and a linear-time removal (O(K)) from a list of size K. In the worst case, K can be O(N), and an incoming order could trigger O(N) matches, leading to an O(N^2) process for a single order. With O(N) such orders, the total complexity can reach O(N^3). · **Space:** O(N), where N is the number of orders. In the worst case, no orders are matched, and all N orders are stored in the backlogs.
**Pros:** Simple to understand and implement as it directly models the problem statement.
**Cons:** Extremely inefficient due to repeated linear scans and list removals.; The time complexity of O(N^3) makes it infeasible for the given constraints, leading to a 'Time Limit Exceeded' error.
### Explanation
We maintain two lists: `buyBacklog` for buy orders and `sellBacklog` for sell orders. When a `buy` order arrives, we repeatedly search for the sell order with the minimum price in the `sellBacklog`. To do this, we must iterate through the entire `sellBacklog` to find the minimum price. If a match is found (sell price <= buy price), we execute the trade, update the amounts, and if the sell order is fully executed, we remove it from the `sellBacklog`. This removal operation on a list also takes time proportional to the list's size. We repeat this process until the buy order is fully filled or no more matches can be found. Any remaining amount of the buy order is added to the `buyBacklog`. A similar process is followed for an incoming `sell` order, where we search for the buy order with the maximum price in the `buyBacklog`. Finally, we sum the amounts of all orders remaining in both backlogs.

```java
// Note: This is a conceptual implementation for demonstration. It is highly inefficient and will time out.
import java.util.ArrayList;
import java.util.List;

class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        List<long[]> buyBacklog = new ArrayList<>(); // [price, amount]
        List<long[]> sellBacklog = new ArrayList<>();

        for (int[] order : orders) {
            long price = order[0];
            long amount = order[1];
            int type = order[2];

            if (type == 0) { // Buy order
                while (amount > 0 && !sellBacklog.isEmpty()) {
                    int bestSellIdx = -1;
                    long minSellPrice = Long.MAX_VALUE;
                    for (int i = 0; i < sellBacklog.size(); i++) {
                        if (sellBacklog.get(i)[0] <= price && sellBacklog.get(i)[0] < minSellPrice) {
                            minSellPrice = sellBacklog.get(i)[0];
                            bestSellIdx = i;
                        }
                    }

                    if (bestSellIdx == -1) {
                        break;
                    }

                    long[] sellOrder = sellBacklog.get(bestSellIdx);
                    long tradeAmount = Math.min(amount, sellOrder[1]);
                    amount -= tradeAmount;
                    sellOrder[1] -= tradeAmount;

                    if (sellOrder[1] == 0) {
                        sellBacklog.remove(bestSellIdx);
                    }
                }
                if (amount > 0) {
                    buyBacklog.add(new long[]{price, amount});
                }
            } else { // Sell order
                while (amount > 0 && !buyBacklog.isEmpty()) {
                    int bestBuyIdx = -1;
                    long maxBuyPrice = Long.MIN_VALUE;
                    for (int i = 0; i < buyBacklog.size(); i++) {
                        if (buyBacklog.get(i)[0] >= price && buyBacklog.get(i)[0] > maxBuyPrice) {
                            maxBuyPrice = buyBacklog.get(i)[0];
                            bestBuyIdx = i;
                        }
                    }

                    if (bestBuyIdx == -1) {
                        break;
                    }

                    long[] buyOrder = buyBacklog.get(bestBuyIdx);
                    long tradeAmount = Math.min(amount, buyOrder[1]);
                    amount -= tradeAmount;
                    buyOrder[1] -= tradeAmount;

                    if (buyOrder[1] == 0) {
                        buyBacklog.remove(bestBuyIdx);
                    }
                }
                if (amount > 0) {
                    sellBacklog.add(new long[]{price, amount});
                }
            }
        }

        long total = 0;
        int MOD = 1_000_000_007;
        for (long[] b : buyBacklog) total = (total + b[1]) % MOD;
        for (long[] s : sellBacklog) total = (total + s[1]) % MOD;
        return (int) total;
    }
}
```
### Algorithm
*   Initialize two lists, `buyBacklog` and `sellBacklog`, to store pending buy and sell orders respectively. Each order is stored as a pair of `[price, amount]`.
*   Iterate through each `order` in the input `orders` array.
*   If the current order is a `buy` order:
    *   Repeatedly search for the sell order with the minimum price in the `sellBacklog` as long as the buy order has `amount > 0`.
    *   This search requires a full linear scan of the `sellBacklog`.
    *   If a sell order is found with `price <=` the buy order's price, execute the trade. Update the amounts of both orders.
    *   If the matched sell order's amount becomes zero, remove it from the `sellBacklog`. This removal operation takes linear time.
    *   If the buy order still has `amount > 0` after the matching loop, add it to the `buyBacklog`.
*   If the current order is a `sell` order, perform a symmetric operation: repeatedly find the buy order with the maximum price in `buyBacklog` and execute trades.
*   After processing all input orders, calculate the total amount of orders remaining in both backlogs. Sum up all `amount` values, taking the result modulo `10^9 + 7`.

## Optimized Simulation with Priority Queues (Heaps)
This approach uses priority queues (heaps) to efficiently manage the backlogs. A max-heap is used for buy orders to quickly find the one with the highest price, and a min-heap is used for sell orders to quickly find the one with the lowest price. This avoids the costly linear scans of the brute-force approach and provides an optimal solution.
**Time:** O(N log N), where N is the number of orders. Each of the N orders is processed. An order is either matched or added to a heap. An order added to a heap is eventually removed. Each heap insertion (`add`) and removal (`poll`) takes O(log K) time, where K is the current size of the heap (K ≤ N). Since each order results in at most one insertion and is part of at most one final removal, the total time complexity is dominated by these heap operations. · **Space:** O(N), where N is the number of orders. In the worst-case scenario where no orders are matched, all N orders will be stored in the heaps.
**Pros:** Highly efficient, with a time complexity that is well within the limits for the given constraints.; The use of heaps is a standard and elegant solution for problems requiring frequent retrieval of min/max elements.
**Cons:** Slightly more complex to implement than a naive list-based approach due to the need to set up priority queues with custom comparators.
### Explanation
The core idea is to use data structures that provide fast access to the required elements. For buy orders, we need to match against the one with the largest price, which is a perfect use case for a max-heap. For sell orders, we need to match against the one with the smallest price, which is a use case for a min-heap.

We maintain two priority queues:
1.  `buyOrders`: A max-heap storing `[price, amount]`, ordered by price descending.
2.  `sellOrders`: A min-heap storing `[price, amount]`, ordered by price ascending.

When a `buy` order arrives, we check the top of the `sellOrders` min-heap. The `peek()` operation gives the best match in `O(1)` time. If a match is possible, we execute the trade. If the sell order from the heap is fully executed, we remove it using `poll()` in `O(log S)` time (where S is the size of the sell heap). This process is repeated until the buy order is filled or no more matches can be found. Any leftover amount is added to the `buyOrders` heap. A symmetric process is followed for incoming `sell` orders. This approach drastically reduces the time complexity of finding matching orders.

```java
import java.util.PriorityQueue;

class Solution {
    public int getNumberOfBacklogOrders(int[][] orders) {
        int MOD = 1_000_000_007;

        // Max-heap for buy orders: [price, amount]
        PriorityQueue<int[]> buyOrders = new PriorityQueue<>((a, b) -> b[0] - a[0]);
        
        // Min-heap for sell orders: [price, amount]
        PriorityQueue<int[]> sellOrders = new PriorityQueue<>((a, b) -> a[0] - b[0]);

        for (int[] order : orders) {
            int price = order[0];
            int amount = order[1];
            int orderType = order[2];

            if (orderType == 0) { // Buy order
                while (amount > 0 && !sellOrders.isEmpty() && sellOrders.peek()[0] <= price) {
                    int[] sellOrder = sellOrders.peek();
                    int tradeAmount = Math.min(amount, sellOrder[1]);
                    
                    amount -= tradeAmount;
                    sellOrder[1] -= tradeAmount;

                    if (sellOrder[1] == 0) {
                        sellOrders.poll();
                    }
                }
                if (amount > 0) {
                    buyOrders.add(new int[]{price, amount});
                }
            } else { // Sell order
                while (amount > 0 && !buyOrders.isEmpty() && buyOrders.peek()[0] >= price) {
                    int[] buyOrder = buyOrders.peek();
                    int tradeAmount = Math.min(amount, buyOrder[1]);

                    amount -= tradeAmount;
                    buyOrder[1] -= tradeAmount;

                    if (buyOrder[1] == 0) {
                        buyOrders.poll();
                    }
                }
                if (amount > 0) {
                    sellOrders.add(new int[]{price, amount});
                }
            }
        }

        long totalAmount = 0;
        while (!buyOrders.isEmpty()) {
            totalAmount = (totalAmount + buyOrders.poll()[1]) % MOD;
        }
        while (!sellOrders.isEmpty()) {
            totalAmount = (totalAmount + sellOrders.poll()[1]) % MOD;
        }

        return (int) totalAmount;
    }
}
```
### Algorithm
*   Initialize a max-heap `buyOrders` for buy orders and a min-heap `sellOrders` for sell orders. In Java, `PriorityQueue` is used. The max-heap requires a custom comparator to sort by price in descending order.
*   Iterate through each `order = [price, amount, type]` from the input.
*   If it's a `buy` order (`type == 0`):
    *   While the buy order's `amount > 0` and the `sellOrders` heap is not empty and its top element's price (`sellOrders.peek()[0]`) is less than or equal to the current buy order's price:
        *   Get the sell order with the minimum price from the heap.
        *   Calculate the `tradeAmount` as the minimum of the buy and sell amounts.
        *   Update both amounts. If the sell order's amount becomes zero, remove it from the heap using `poll()`.
    *   If the buy order has any remaining `amount`, add it to the `buyOrders` max-heap.
*   If it's a `sell` order (`type == 1`):
    *   Perform a symmetric process using the `buyOrders` max-heap. Match with buy orders whose price is greater than or equal to the sell order's price.
*   After iterating through all orders, calculate the total amount of orders remaining in both heaps. Sum up the amounts, ensuring the calculation is done modulo `10^9 + 7`.

# Solutions
### Java

```java
class Solution { public int getNumberOfBacklogOrders ( int [][] orders ) { PriorityQueue < int []> buy = new PriorityQueue <>(( a , b ) -> b [ 0 ] - a [ 0 ]); PriorityQueue < int []> sell = new PriorityQueue <>(( a , b ) -> a [ 0 ] - b [ 0 ]); for ( var e : orders ) { int p = e [ 0 ], a = e [ 1 ], t = e [ 2 ]; if ( t == 0 ) { while ( a > 0 && ! sell . isEmpty () && sell . peek ()[ 0 ] <= p ) { var q = sell . poll (); int x = q [ 0 ], y = q [ 1 ]; if ( a >= y ) { a -= y ; } else { sell . offer ( new int [] { x , y - a }); a = 0 ; } } if ( a > 0 ) { buy . offer ( new int [] { p , a }); } } else { while ( a > 0 && ! buy . isEmpty () && buy . peek ()[ 0 ] >= p ) { var q = buy . poll (); int x = q [ 0 ], y = q [ 1 ]; if ( a >= y ) { a -= y ; } else { buy . offer ( new int [] { x , y - a }); a = 0 ; } } if ( a > 0 ) { sell . offer ( new int [] { p , a }); } } } long ans = 0 ; final int mod = ( int ) 1 e9 + 7 ; while (! buy . isEmpty ()) { ans += buy . poll ()[ 1 ]; } while (! sell . isEmpty ()) { ans += sell . poll ()[ 1 ]; } return ( int ) ( ans % mod ); } }
```

### CPP

```cpp
class Solution { public: int getNumberOfBacklogOrders ( vector < vector < int >>& orders ) { using pii = pair < int , int > ; priority_queue < pii , vector < pii > , greater < pii >> sell ; priority_queue < pii > buy ; for ( auto & e : orders ) { int p = e [ 0 ], a = e [ 1 ], t = e [ 2 ]; if ( t == 0 ) { while ( a && ! sell . empty () && sell . top (). first <= p ) { auto [ x , y ] = sell . top (); sell . pop (); if ( a >= y ) { a -= y ; } else { sell . push ({ x , y - a }); a = 0 ; } } if ( a ) { buy . push ({ p , a }); } } else { while ( a && ! buy . empty () && buy . top (). first >= p ) { auto [ x , y ] = buy . top (); buy . pop (); if ( a >= y ) { a -= y ; } else { buy . push ({ x , y - a }); a = 0 ; } } if ( a ) { sell . push ({ p , a }); } } } long ans = 0 ; while ( ! buy . empty ()) { ans += buy . top (). second ; buy . pop (); } while ( ! sell . empty ()) { ans += sell . top (). second ; sell . pop (); } const int mod = 1e9 + 7 ; return ans % mod ; } };
```

### Python

```python
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
```