The "Number of Orders in the Backlog" problem asks you to process a sequence of buy and sell orders in a stock market simulation. Each order is represented by an array of three integers: [price, amount, orderType], where orderType is 0 for a buy order and 1 for a sell order.
The rules are:
10^9 + 7.At first glance, the problem seems to require matching orders in a straightforward manner. A brute-force approach would involve scanning all existing orders in the backlog to find matches for each new order, but this would be inefficient for large inputs.
To optimize, we need a way to always quickly access the best possible match for any incoming order:
We'll use two heaps (priority queues) to efficiently manage and access the orders in the backlog:
10^9 + 7.We use heaps because they allow us to always access the "best" order to match in logarithmic time, rather than searching through all orders.
Sample Input:
orders = [
[10, 5, 0], // buy 5 at price 10
[15, 2, 1], // sell 2 at price 15
[25, 1, 1], // sell 1 at price 25
[30, 4, 0] // buy 4 at price 30
]
Step-by-step:
Brute-force approach:
The use of heaps ensures efficient access to the best matching order and keeps the solution scalable for large inputs.
We efficiently solve the "Number of Orders in the Backlog" problem by using two heaps to always access the best matching buy or sell order for each incoming order. This approach avoids brute-force scanning and leverages the properties of heaps for quick access and updates, resulting in an elegant and scalable solution. The key insight is to process orders greedily using appropriate data structures to maintain the backlog efficiently.
import heapq
class Solution:
def getNumberOfBacklogOrders(self, orders):
MOD = 10**9 + 7
buy_heap = [] # max-heap (invert price)
sell_heap = [] # min-heap
for price, amount, orderType in orders:
if orderType == 0:
# Buy order
while amount > 0 and sell_heap and sell_heap[0][0] <= price:
sell_price, sell_amount = heapq.heappop(sell_heap)
matched = min(amount, sell_amount)
amount -= matched
sell_amount -= matched
if sell_amount > 0:
heapq.heappush(sell_heap, (sell_price, sell_amount))
if amount > 0:
heapq.heappush(buy_heap, (-price, amount))
else:
# Sell order
while amount > 0 and buy_heap and -buy_heap[0][0] >= price:
buy_price, buy_amount = heapq.heappop(buy_heap)
matched = min(amount, buy_amount)
amount -= matched
buy_amount -= matched
if buy_amount > 0:
heapq.heappush(buy_heap, (buy_price, buy_amount))
if amount > 0:
heapq.heappush(sell_heap, (price, amount))
total = 0
for _, amount in buy_heap:
total = (total + amount) % MOD
for _, amount in sell_heap:
total = (total + amount) % MOD
return total
#include <vector>
#include <queue>
using namespace std;
class Solution {
public:
int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
const int MOD = 1e9 + 7;
// max-heap for buy: highest price first
priority_queue<pair<int, int>> buy;
// min-heap for sell: lowest price first
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> sell;
for (auto& order : orders) {
int price = order[0], amount = order[1], type = order[2];
if (type == 0) {
// Buy order
while (amount > 0 && !sell.empty() && sell.top().first <= price) {
auto [sellPrice, sellAmount] = sell.top();
sell.pop();
int matched = min(amount, sellAmount);
amount -= matched;
sellAmount -= matched;
if (sellAmount > 0) sell.push({sellPrice, sellAmount});
}
if (amount > 0) buy.push({price, amount});
} else {
// Sell order
while (amount > 0 && !buy.empty() && buy.top().first >= price) {
auto [buyPrice, buyAmount] = buy.top();
buy.pop();
int matched = min(amount, buyAmount);
amount -= matched;
buyAmount -= matched;
if (buyAmount > 0) buy.push({buyPrice, buyAmount});
}
if (amount > 0) sell.push({price, amount});
}
}
long long total = 0;
while (!buy.empty()) {
total = (total + buy.top().second) % MOD;
buy.pop();
}
while (!sell.empty()) {
total = (total + sell.top().second) % MOD;
sell.pop();
}
return (int)total;
}
};
import java.util.*;
class Solution {
public int getNumberOfBacklogOrders(int[][] orders) {
int MOD = 1_000_000_007;
// Max-heap for buy orders
PriorityQueue<int[]> buy = new PriorityQueue<>((a, b) -> b[0] - a[0]);
// Min-heap for sell orders
PriorityQueue<int[]> sell = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int[] order : orders) {
int price = order[0], amount = order[1], type = order[2];
if (type == 0) {
// Buy order
while (amount > 0 && !sell.isEmpty() && sell.peek()[0] <= price) {
int[] top = sell.poll();
int matched = Math.min(amount, top[1]);
amount -= matched;
top[1] -= matched;
if (top[1] > 0) sell.offer(top);
}
if (amount > 0) buy.offer(new int[]{price, amount});
} else {
// Sell order
while (amount > 0 && !buy.isEmpty() && buy.peek()[0] >= price) {
int[] top = buy.poll();
int matched = Math.min(amount, top[1]);
amount -= matched;
top[1] -= matched;
if (top[1] > 0) buy.offer(top);
}
if (amount > 0) sell.offer(new int[]{price, amount});
}
}
long total = 0;
for (int[] order : buy) total = (total + order[1]) % MOD;
for (int[] order : sell) total = (total + order[1]) % MOD;
return (int)total;
}
}
class Heap {
constructor(cmp) {
this.data = [];
this.cmp = cmp;
}
push(val) {
this.data.push(val);
this._up(this.data.length - 1);
}
pop() {
if (this.size() === 0) return null;
const top = this.data[0];
const last = this.data.pop();
if (this.data.length > 0) {
this.data[0] = last;
this._down(0);
}
return top;
}
peek() {
return this.data[0];
}
size() {
return this.data.length;
}
_up(idx) {
while (idx > 0) {
let parent = (idx - 1) >> 1;
if (this.cmp(this.data[idx], this.data[parent]) < 0) {
[this.data[idx], this.data[parent]] = [this.data[parent], this.data[idx]];
idx = parent;
} else break;
}
}
_down(idx) {
let n = this.data.length;
while (true) {
let left = idx * 2 + 1, right = idx * 2 + 2, smallest = idx;
if (left < n && this.cmp(this.data[left], this.data[smallest]) < 0) smallest = left;
if (right < n && this.cmp(this.data[right], this.data[smallest]) < 0) smallest = right;
if (smallest !== idx) {
[this.data[idx], this.data[smallest]] = [this.data[smallest], this.data[idx]];
idx = smallest;
} else break;
}
}
}
var getNumberOfBacklogOrders = function(orders) {
const MOD = 1e9 + 7;
// Max-heap for buy (by price descending)
let buy = new Heap((a, b) => b[0] - a[0]);
// Min-heap for sell (by price ascending)
let sell = new Heap((a, b) => a[0] - b[0]);
for (let [price, amount, type] of orders) {
if (type === 0) {
// Buy order
while (amount > 0 && sell.size() && sell.peek()[0] <= price) {
let [sellPrice, sellAmount] = sell.pop();
let matched = Math.min(amount, sellAmount);
amount -= matched;
sellAmount -= matched;
if (sellAmount > 0) sell.push([sellPrice, sellAmount]);
}
if (amount > 0) buy.push([price, amount]);
} else {
// Sell order
while (amount > 0 && buy.size() && buy.peek()[0] >= price) {
let [buyPrice, buyAmount] = buy.pop();
let matched = Math.min(amount, buyAmount);
amount -= matched;
buyAmount -= matched;
if (buyAmount > 0) buy.push([buyPrice, buyAmount]);
}
if (amount > 0) sell.push([price, amount]);
}
}
let total = 0;
for (let [_, amt] of buy.data) total = (total + amt) % MOD;
for (let [_, amt] of sell.data) total = (total + amt) % MOD;
return total;
};