Leetcode 1801. Number of Orders in the Backlog Solution

Problem Explanation:

In this problem, we are given a list of orders where each order is represented as a list containing three values [price, amount, orderType]. Here, orderType can either be 0 (buy order) or 1 (sell order). There is a backlog of orders that have not been executed yet. When a new order is placed, it will either match with an existing order in the backlog and get executed, or will be added to the backlog if no match is found.

Our task is to find the total amount of orders left in the backlog after placing all the input orders.

Approach:

In order to solve this problem efficiently, we will use two priority queues to maintain the buy and sell orders in the backlog.

  1. buysMaxHeap: A max heap to store the buy orders, sorted in descending order by price.
  2. sellsMinHeap: A min heap to store the sell orders, sorted in ascending order by price.

Now, for each order in the input, we perform the following steps:

  • If it's a buy order, add it to the buysMaxHeap.
  • If it's a sell order, add it to the sellsMinHeap.
  • Check if the top buy order in buysMaxHeap can be matched with the top sell order in sellsMinHeap, i.e., the buy order price is greater than or equal to the sell order price.
  • If a match is found, execute the orders and update the heaps accordingly.
  • Repeat the process until no match is found or one of the heaps becomes empty.

After processing all orders, calculate the total amount of orders remaining in the backlog by summing the amounts in both heaps.

Finally, return the result modulo 10^9 + 7 since the total number can be large.

Solution:

1class Solution {
2 public:
3  int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
4    constexpr int kMod = 1'000'000'007;
5    int ans = 0;
6    // Using max heap for buy orders
7    priority_queue<vector<int>> buysMaxHeap;
8    // Using min heap for sell orders
9    priority_queue<vector<int>, vector<vector<int>>, greater<>> sellsMinHeap;
10
11    for (const vector<int>& order : orders) {
12      if (order[2] == 0)
13        buysMaxHeap.push(order);
14      else
15        sellsMinHeap.push(order);
16        
17      // Checking if top buy order can be matched with top sell order
18      while (!buysMaxHeap.empty() && !sellsMinHeap.empty() &&
19             buysMaxHeap.top()[0] >= sellsMinHeap.top()[0]) {
20        const int minAmount = min(buysMaxHeap.top()[1], sellsMinHeap.top()[1]);
21        
22        // Executing matching orders and updating heaps
23        vector<int> buysMaxHeapTop = buysMaxHeap.top();
24        buysMaxHeap.pop();
25        buysMaxHeapTop[1] -= minAmount;
26        if (buysMaxHeapTop[1] > 0)
27          buysMaxHeap.push(buysMaxHeapTop);
28
29        vector<int> sellsMinHeapTop = sellsMinHeap.top();
30        sellsMinHeap.pop();
31        sellsMinHeapTop[1] -= minAmount;
32        if (sellsMinHeapTop[1] > 0)
33          sellsMinHeap.push(sellsMinHeapTop);
34      }
35    }
36
37    // Calculating the total amount of orders left in the backlog
38    while (!buysMaxHeap.empty()) {
39      ans += buysMaxHeap.top()[1], buysMaxHeap.pop();
40      ans %= kMod;
41    }
42
43    while (!sellsMinHeap.empty()) {
44      ans += sellsMinHeap.top()[1], sellsMinHeap.pop();
45      ans %= kMod;
46    }
47
48    return ans;
49  }
50};

Now you can understand from the explanation and the solution above how we can use priority queues to efficiently find the total amount of orders left in the backlog after placing all the given orders.