1801. Number of Orders in the Backlog

Problem Description

In this problem, you are managing a system that handles buy and sell orders for stocks. Orders are represented by a 2D array where every sub-array consists of three elements: the price, the amount, and the type (0 for buy, 1 for sell). The orders are processed sequentially, and each order can lead to trades if a matching order of the opposite type is found in the backlog. The backlog is a list of orders that have not yet been executed because there wasn't a matching order at the time they were placed.

The rules for executing trades are as follows:

• If a buy order is placed, the system looks for the lowest-priced sell order in the backlog. If a match is found (i.e., a sell order with a price less than or equal to the buy order), they are executed and removed from the backlog. Otherwise, the buy order goes into the backlog.
• Conversely, for a sell order, the system looks for the highest-priced buy order in the backlog. If a match is found (i.e., a buy order with a price greater than or equal to the sell order), they are executed. If not, the sell order goes into the backlog.

The goal is to find the total amount of all orders left in the backlog after all the orders have been processed, and since the number could be very large, it must be returned modulo (10^9 + 7).

Intuition

Given the nature of the order matching system, we can immediately think of priority queues to manage the backlog because priority queues allow us to efficiently access the smallest or largest element, as required by the problem. In Python, priority queues can be implemented using the heapq module.

For buy orders, we want to be able to quickly access the largest price (the most the buyer is willing to pay). Therefore, we use a max-heap for the buy backlog. However, heapq only provides a min-heap implementation, so we insert prices as negative values to mimic a max-heap.

For sell orders, we want to find the sell order with the smallest price (the least the seller is willing to accept), and since heapq is a min-heap, it suits our needs perfectly.

The intuition behind the solution is to iterate through each order in the input:

• For a buy order, check if there’s a match in the sell priority queue and execute trades until there's no more to execute or the backlog is exhausted. Add any remaining orders to the backlog.
• For a sell order, do the same, but check against the buy priority queue for the highest price.
• Keep removing matched orders from the backlog and update their amounts accordingly until no matching orders are left.
• Add the remaining amount of an order to the respective backlog if it couldn't be fully executed.

Finally, we'll have both buy and sell backlogs with unexecuted orders. The sum of the amounts of these orders, modulo (10^9 + 7), is the answer.

Learn more about Heap (Priority Queue) patterns.

Solution Approach

The implemented solution approach uses the heapq module to create two priority queues: one for buy orders and one for sell orders. Let's break down the steps of the implementation:

1. Initialize Priority Queues: Two empty lists, buy and sell, are initialized to act as the max-heap and min-heap, respectively.

2. Processing Orders:

   • Loop through each order in the input orders.

   • Check the order type. If it is a buy order (indicated by t == 0), we process against the sell queue:

     • While there is an amount of the buy order left (a > 0), and there are sell orders in the backlog (sell) with a price that is less than or equal to the current buy order price (sell[0][0] <= p), we try to execute the orders.
     • Pop the smallest-priced sell order from the sell heap.
     • Compare the amounts of the current buy order and the sell order (y). If the current buy order amount is more or equal, reduce its amount by y.
     • If the sell order amount is greater, put back the difference (the rest of the sell order that wasn't executed) into the sell heap.
     • If after all possible matches there's still an amount left of the current buy order, insert it into the buy heap with its price as a negative number to maintain the max-heap property ((-p, a)).

   • If it is a sell order (indicated by t == 1), we follow similar steps against the buy queue. Since buy is a max-heap with negative prices, we compare with -buy[0][0].

3. Calculate the Final Backlog:

   • Remaining unexecuted orders are still in the buy and sell heaps. We calculate the sum of their amounts.
   • Since Python's heap is actually a list, we can sum over buy and sell heaps directly using list comprehension.
   • Due to the possibility of a large sum, we return the final total amount modulo 10**9 + 7 to fit into the problem's requirement for large number management.

The code primarily revolves around the use of heaps and the properties of min-heap and max-heap structures to maintain and manage orders efficiently, ensuring that matching orders are executed and the rest are stored in the backlog. This leads to the desired final count of unmatchable orders left in the backlog, which we calculate in the last step.

By understanding and applying basic data structures like heaps, we can solve complex problems such as this with relative ease and efficiency, resulting in a clean and optimal solution.

Example Walkthrough

Let's assume we have the following small set of stock orders to illustrate the solution approach:

1orders = [[7, 2, 0], [8, 1, 1], [6, 3, 0], [7, 2, 1]]

Each sub-array comprises a price, an amount, and a type ([price, amount, type]). Type '0' is a buy order, and type '1' is a sell order.

1. Initialize Priority Queues: We start with empty buy and sell queues.

2. Processing Orders:

   • First order [7, 2, 0] is a buy order. Since the sell queue is empty, we add this order to the buy queue as (-7, 2).
   • The buy queue now has [(-7, 2)].
   • Next, the order [8, 1, 1] is a sell order. There's a buy order in the buy queue. We compare 8 with the negative of the max price in the buy queue, which is -(-7) = 7. Since 8 > 7, we add the sell order to the sell queue.
   • The sell queue now has [(8, 1)].
   • The third order [6, 3, 0] is another buy order. We check the sell queue for a price less than or equal to 6. No such order exists, so we put [(-6, 3)] into the buy queue, resulting in buy queue: [(-7, 2), (-6, 3)].
   • The final order [7, 2, 1] is a sell order. We match it with the highest priced buy order in the buy queue. The top buy order is for a price of 7, which matches the sell order price, so we execute this trade.
   • We remove one order from buy with 2 amount and one from sell with 2 amount. The buy order is fully executed and removed, but the sell queue was empty before, so nothing changes there.
   • The final buy queue has [(-6, 3)], and the sell queue remains [(8, 1)].

3. Calculate the Final Backlog:

   • The remaining unexecuted buy order is for an amount of 3 and the unexecuted sell order for 1.
   • We sum these amounts to get the total amount in the backlog: 3 + 1 = 4.
   • Since we're asked to return this total modulo (10^9 + 7), we would perform this operation if necessary. However, since 4 is less than (10^9 + 7), the final returned total backlog amount is 4.

By following the steps in the solution approach, we have processed a set of orders and determined the total amount left in the backlog, adhering to the rules of trade execution provided in the given details.

Python Solution

1from heapq import heappop, heappush
2from typing import List
3
4class Solution:
5    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
6        # Define min-heaps for buy and sell orders
7        buy_heap = []
8        sell_heap = []
9      
10        # Iterate over each order
11        for price, amount, order_type in orders:
12            if order_type == 0:  # This is a buy order
13                # Process as much of this order as possible using sell orders that have a price <= current buy order's price
14                while amount > 0 and sell_heap and sell_heap[0][0] <= price:
15                    sell_price, sell_amount = heappop(sell_heap)
16                    if amount >= sell_amount:
17                        amount -= sell_amount
18                    else:
19                        heappush(sell_heap, (sell_price, sell_amount - amount))
20                        amount = 0
21                # If there's any amount left, push it onto the buy heap
22                if amount > 0:
23                    heappush(buy_heap, (-price, amount))
24            else:  # This is a sell order
25                # Process as much of this order as possible using buy orders that have a price >= current sell order's price
26                while amount > 0 and buy_heap and -buy_heap[0][0] >= price:
27                    buy_price, buy_amount = heappop(buy_heap)
28                    if amount >= buy_amount:
29                        amount -= buy_amount
30                    else:
31                        heappush(buy_heap, (buy_price, buy_amount - amount))
32                        amount = 0
33                # If there's any amount left, push it onto the sell heap
34                if amount > 0:
35                    heappush(sell_heap, (price, amount))
36      
37        # Compute the sum of the amounts of orders left in the heaps
38        mod = 10**9 + 7
39        total_amount_left = sum(order[1] for order in buy_heap + sell_heap) % mod
40      
41        return total_amount_left
42

Java Solution

1class Solution {
2    public int getNumberOfBacklogOrders(int[][] orders) {
3        // A priority queue to store buy orders with the highest price at the top.
4        PriorityQueue<int[]> buyQueue = new PriorityQueue<>((a, b) -> b[0] - a[0]);
5        // A priority queue to store sell orders with the lowest price at the top.
6        PriorityQueue<int[]> sellQueue = new PriorityQueue<>((a, b) -> a[0] - b[0]);
7      
8        for (int[] order : orders) {
9            int price = order[0], amount = order[1], orderType = order[2];
10          
11            // Processing for a buy order.
12            if (orderType == 0) {
13                // Attempt to fulfill the buy order with available sell orders.
14                while (amount > 0 && !sellQueue.isEmpty() && sellQueue.peek()[0] <= price) {
15                    int[] sellOrder = sellQueue.poll();
16                    int sellPrice = sellOrder[0], sellAmount = sellOrder[1];
17                    if (amount >= sellAmount) {
18                        amount -= sellAmount;
19                    } else {
20                        // Partially fulfill the buy order and put the remaining sell order back.
21                        sellQueue.offer(new int[] {sellPrice, sellAmount - amount});
22                        amount = 0;
23                    }
24                }
25                // If there is an outstanding amount, add the buy order to the backlog.
26                if (amount > 0) {
27                    buyQueue.offer(new int[] {price, amount});
28                }
29            } else {
30                // Processing for a sell order.
31                // Attempt to fulfill the sell order with available buy orders.
32                while (amount > 0 && !buyQueue.isEmpty() && buyQueue.peek()[0] >= price) {
33                    int[] buyOrder = buyQueue.poll();
34                    int buyPrice = buyOrder[0], buyAmount = buyOrder[1];
35                    if (amount >= buyAmount) {
36                        amount -= buyAmount;
37                    } else {
38                        // Partially fulfill the sell order and put the remaining buy order back.
39                        buyQueue.offer(new int[] {buyPrice, buyAmount - amount});
40                        amount = 0;
41                    }
42                }
43                // If there is an outstanding amount, add the sell order to the backlog.
44                if (amount > 0) {
45                    sellQueue.offer(new int[] {price, amount});
46                }
47            }
48        }
49      
50        // Calculate the total number of backlog orders.
51        long backlogCount = 0;
52        final int modulo = (int) 1e9 + 7;
53      
54        // Sum the amounts from all buy backlog orders.
55        while (!buyQueue.isEmpty()) {
56            backlogCount += buyQueue.poll()[1];
57        }
58        // Sum the amounts from all sell backlog orders.
59        while (!sellQueue.isEmpty()) {
60            backlogCount += sellQueue.poll()[1];
61        }
62      
63        // Return the total backlog count modulo 1e9 + 7.
64        return (int) (backlogCount % modulo);
65    }
66}
67

C++ Solution

1#include <vector>
2#include <queue>
3#include <utility>
4
5class Solution {
6public:
7    int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
8        using OrderPair = pair<int, int>; // Use pair to represent order with price and amount
9        priority_queue<OrderPair, vector<OrderPair>, greater<OrderPair>> sellOrders; // Min-heap for sell orders
10        priority_queue<OrderPair> buyOrders; // Max-heap for buy orders
11      
12        for (auto& order : orders) {
13            int price = order[0], amount = order[1], type = order[2];
14          
15            if (type == 0) { // Buy order
16                // Match with existing sell orders if possible
17                while (amount > 0 && !sellOrders.empty() && sellOrders.top().first <= price) {
18                    auto [sellPrice, sellAmount] = sellOrders.top();
19                    sellOrders.pop();
20                    if (amount >= sellAmount) {
21                        amount -= sellAmount;
22                    } else {
23                        sellOrders.push({sellPrice, sellAmount - amount});
24                        amount = 0;
25                    }
26                }
27                // If there's leftover amount, push it into buy orders
28                if (amount > 0) {
29                    buyOrders.push({price, amount});
30                }
31            } else { // Sell order
32                // Match with existing buy orders if possible
33                while (amount > 0 && !buyOrders.empty() && buyOrders.top().first >= price) {
34                    auto [buyPrice, buyAmount] = buyOrders.top();
35                    buyOrders.pop();
36                    if (amount >= buyAmount) {
37                        amount -= buyAmount;
38                    } else {
39                        buyOrders.push({buyPrice, buyAmount - amount});
40                        amount = 0;
41                    }
42                }
43                // If there's leftover amount, push it into sell orders
44                if (amount > 0) {
45                    sellOrders.push({price, amount});
46                }
47            }
48        }
49      
50        long totalBacklog = 0; // To count total backlog amount
51        // Sum all amounts in buyOrders backlog
52        while (!buyOrders.empty()) {
53            totalBacklog += buyOrders.top().second;
54            buyOrders.pop();
55        }
56        // Sum all amounts in sellOrders backlog
57        while (!sellOrders.empty()) {
58            totalBacklog += sellOrders.top().second;
59            sellOrders.pop();
60        }
61
62        const int MOD = 1e9 + 7; // Use constant value for the modulo operation
63        // Return the total backlog amount modulo 1e9 + 7
64        return totalBacklog % MOD;
65    }
66};
67

Typescript Solution

1type OrderPair = [number, number]; // Tuple to represent order with price and amount
2
3let sellOrders: OrderPair[] = []; // Array to simulate min-heap for sell orders
4let buyOrders: OrderPair[] = []; // Array to simulate max-heap for buy orders
5
6// Define a compare function for min-heap
7function minHeapCompare(a: OrderPair, b: OrderPair): number {
8    return a[0] - b[0];
9}
10
11// Define a compare function for max-heap
12function maxHeapCompare(a: OrderPair, b: OrderPair): number {
13    return b[0] - a[0];
14}
15
16// Utility function to push to a heap and then sort it
17function heapPush(heap: OrderPair[], element: OrderPair, compareFunction: (a: OrderPair, b: OrderPair) => number): void {
18    heap.push(element);
19    heap.sort(compareFunction);
20}
21
22// Utility function to pop from a heap assuming it's already sorted
23function heapPop(heap: OrderPair[]): OrderPair | undefined {
24    return heap.shift();
25}
26
27function getNumberOfBacklogOrders(orders: number[][]): number {
28    for (let order of orders) {
29        let price = order[0], amount = order[1], type = order[2];
30      
31        // Handle buy order
32        if (type === 0) {
33            while (amount > 0 && sellOrders.length > 0 && sellOrders[0][0] <= price) {
34                let [sellPrice, sellAmount] = heapPop(sellOrders)!;
35                if (amount >= sellAmount) {
36                    amount -= sellAmount;
37                } else {
38                    heapPush(sellOrders, [sellPrice, sellAmount - amount], minHeapCompare);
39                    amount = 0;
40                }
41            }
42            if (amount > 0) {
43                heapPush(buyOrders, [price, amount], maxHeapCompare);
44            }
45        } else { // Handle sell order
46            while (amount > 0 && buyOrders.length > 0 && buyOrders[0][0] >= price) {
47                let [buyPrice, buyAmount] = heapPop(buyOrders)!;
48                if (amount >= buyAmount) {
49                    amount -= buyAmount;
50                } else {
51                    heapPush(buyOrders, [buyPrice, buyAmount - amount], maxHeapCompare);
52                    amount = 0;
53                }
54            }
55            if (amount > 0) {
56                heapPush(sellOrders, [price, amount], minHeapCompare);
57            }
58        }
59    }
60  
61    let totalBacklog = 0;
62    // Sum all amounts in buyOrders backlog
63    buyOrders.forEach((order) => totalBacklog += order[1]);
64    // Sum all amounts in sellOrders backlog
65    sellOrders.forEach((order) => totalBacklog += order[1]);
66
67    const MOD = 1e9 + 7;
68    // Return the total backlog amount modulo 1e9 + 7
69    return totalBacklog % MOD;
70}
71

Time and Space Complexity

Time Complexity

The time complexity of the getNumberOfBacklogOrders function primarily depends on the number of orders being processed and the operations performed on the heap for buy and sell orders.

For each order, we:

• Potentially perform a while loop, which can iterate at most 'a' times, where 'a' is the amount of the current order.
• Perform heap operations heappop and heappush, which have a time complexity of O(log n) each, where 'n' is the number of orders in the heap.

However, since each order is only processed once and we push/pop it from the heap, we can simplify the time complexity analysis to concentrating on the heap operations.

The worst-case scenario is when each order interacts with the heap, leading to O(n log n) time complexity, where 'n' is the total number of orders. This is due to the fact that potentially each order could result in a heappop and a heappush.

Space Complexity

The space complexity is determined by the space required to store the buy and sell heaps. In the worst case, all orders could end up in one of the heaps if they cannot be matched and executed.

Therefore, the space complexity is O(n), where 'n' is the total number of orders.

Learn more about how to find time and space complexity quickly.