Table of Contents
Problem Statement
The Number of Orders in the Backlog LeetCode Solution – “Number of Orders in the Backlog” states that given the 2D integer array [price, amount, orderType] which denotes that amount orders have been placed of type order type.
If the order type is :
- 0, denotes the current order is a buy order.
- 1, denotes the current order is a sell order.
Note that order[i] will be executed when all orders before ith order are executed.
A Backlog is defined as orders that are not executed. Initially, there is no backlog for buy as well as sell orders, the following happens:
- If the order is a buy order, look at the sell order with the smallest price in the backlog. If the selling price is less than or equal to the current buy order price, then there is a match and the sell order in the backlog is executed and removed.
- Vice versa, when there is a sell order, look at the buy order with the largest price in the backlog. If the buying price is greater than or equal to the current sell order price, then there is a match and the buy order in the backlog is executed and removed.
We need to return the total amount of orders in the backlog after placing all the orders from the input. Return the answer modulo 10^9 + 7.
Example:
Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6
Explanation:
- Initially, 5 buy orders are placed and there are no sell orders in the backlog hence, all the buy orders are added to the buy backlog.
- 2 sell orders are placed and there are no buy orders with prices larger than or equal to 15 hence, all the orders are added to the sell 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 with type buy are placed each having the amount 30. 2 sell orders with price 15 are removed. Again, 1 sell order with a price of 25 is also removed. 4th order is added to the backlog since there are no more sell orders in the backlog.
- Finally, the backlog has 5 buy orders with a price of 10, and 1 buy order with a price of 30. So, the total number of orders in the backlog is 6.
Input: orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
Output: 999999984
Approach
Idea:
- The main idea to solve this problem is to use Priority Queue or Multiset to insert or remove buy or sell orders in the backlog efficiently.
- Maintain a heap or multiset separately for buy and sell backlogs.
- Start processing orders sequentially, and for each order:
- If it is a buy order, erase all entries from sell order backlogs whose price is less than or equal to the current order price, starting from the smallest selling order backlog price.
- Vice Versa, If it is a sell order, erase all entries from buy order backlogs whose price is greater than or equal to the current order price, starting from the largest buying order backlog price.
- When we’re done with all the orders, add all the amounts of the orders which are present in the buy and sell backlogs.
- Note that our answer may exceed the value 10^9 + 7, we need to take the answer modulo this prime number.
Code
Number of Orders in the Backlog Leetcode C++ Solution:
class Solution {
public:
#define ll long long
#define MOD 1000000007
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
ll ans = 0;
multiset<pair<int,int>> sell;
multiset<pair<int,int>,greater<pair<int,int>>> buy;
for(auto& order:orders){
int price = order[0],amount = order[1],orderType = order[2];
if(orderType==0){
while(!sell.empty() and amount>0 and sell.begin()->first<=price){
int available_price = sell.begin()->first;
int available_amount = sell.begin()->second;
sell.erase(sell.begin());
int take = min(amount,available_amount);
amount -= take;
available_amount -= take;
if(available_amount){
sell.insert({available_price,available_amount});
}
}
if(amount){
buy.insert({price,amount});
}
}
else{
while(!buy.empty() and amount>0 and buy.begin()->first>=price){
int available_price = buy.begin()->first;
int available_amount = buy.begin()->second;
buy.erase(buy.begin());
int take = min(amount,available_amount);
amount -= take;
available_amount -= take;
if(available_amount){
buy.insert({available_price,available_amount});
}
}
if(amount){
sell.insert({price,amount});
}
}
}
for(auto& x:buy){
ans += x.second;
ans %= MOD;
}
for(auto& x:sell){
ans += x.second;
ans %= MOD;
}
return (int)ans;
}
};Number of Orders in the Backlog Leetcode Java Solution:
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 (int[] order : orders) {
if (order[2] == 0){
buy.offer(order);
}
else{
sell.offer(order);
}
while (!buy.isEmpty() && !sell.isEmpty() && sell.peek()[0] <= buy.peek()[0]) {
int k = Math.min(buy.peek()[1], sell.peek()[1]);
buy.peek()[1] -= k;
sell.peek()[1] -= k;
if (buy.peek()[1] == 0) buy.poll();
if (sell.peek()[1] == 0) sell.poll();
}
}
int res = 0, mod = 1000000007;
for (int[] order : sell){
res = (res + order[1]) % mod;
}
for (int[] order : buy){
res = (res + order[1]) % mod;
}
return res;
}
}Complexity Analysis for Number of Orders in the Backlog Leetcode Solution
Time Complexity
The time complexity of the above code is O(NlogN), where N = a total number of orders. For each order, we’re inserting the data into multiset or heap and removing them which takes logN time.
Space Complexity
The space complexity of the above code is O(N). In the worst case, the size of the heap or multiset can take all orders.