Number of Orders in the Backlog — Medium Problem & Solution

orders[i] = [price, amount, orderType] places amount orders of type 0 (buy) or 1 (sell) at that price.

Difficulty: Medium
Topics: Arrays, Simulation, Heap
Asked at: Amazon, Google, Morgan Stanley
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

orders[i] = [price, amount, orderType] places amount orders of type 0 (buy) or 1 (sell) at that price. They arrive in the given order and are handled one at a time.

A buy order is matched against the cheapest sell in the backlog whenever that price is at most the buy price; a sell order is matched against the most expensive buy whenever that price is at least the sell price. Each match cancels one order from each side. Whatever cannot be matched joins the backlog.

Return the total number of orders left in the backlog, modulo 10^9 + 7.

Example 1

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6
Explanation: The last buy clears both sells; 5 buys at 10 and 1 buy at 30 remain.

Example 2

Input: orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
Output: 999999984

Example 3

Input: orders = [[1,1,0],[1,1,1]]
Output: 0
Explanation: The sell matches the buy exactly.

Constraints

1 <= orders.length <= 10^5
orders[i].length == 3
1 <= price, amount <= 10^9
orderType is 0 or 1

How to solve Number of Orders in the Backlog

Simulate the exchange with two heaps: buys ordered by highest price, sells by lowest. Each arriving order eats into the opposite heap's top entry while the price condition holds; the remainder is pushed onto its own side.

Approach

For a buy at price, while the cheapest sell is at most price, cancel min(amount, thatEntry) from both.
For a sell, do the mirror image against the most expensive buy.
Push whatever is left of the incoming order onto its own heap.
Finally sum the remaining amounts modulo 10^9 + 7.

Why it works

Storing a quantity per heap entry rather than one entry per order is what makes the simulation feasible: a single line may carry 10^9 orders. The running total also needs a 64-bit accumulator — up to 10^5 lines of 10^9 each is 10^14, far past a 32-bit int, so the modulus is applied to the sum rather than the comparisons.

Complexity

Time — O(n log n)
Space — O(n)

Pitfalls

Expanding each order into individual units does not fit in memory.
The modulus applies only to the final count, never to the prices or the matching.
A partially matched entry stays on the heap with its reduced quantity.

Reference solution

Python

from typing import List
import heapq

def getNumberOfBacklogOrders(orders: List[List[int]]) -> int:
    MOD = 1000000007
    buy = []   # max-heap by price, stored negated
    sell = []  # min-heap by price
    for price, amount, kind in orders:
        amt = amount
        if kind == 0:
            while amt > 0 and sell and sell[0][0] <= price:
                p, q = heapq.heappop(sell)
                take = min(amt, q)
                amt -= take
                q -= take
                if q:
                    heapq.heappush(sell, (p, q))
            if amt:
                heapq.heappush(buy, (-price, amt))
        else:
            while amt > 0 and buy and -buy[0][0] >= price:
                p, q = heapq.heappop(buy)
                take = min(amt, q)
                amt -= take
                q -= take
                if q:
                    heapq.heappush(buy, (p, q))
            if amt:
                heapq.heappush(sell, (price, amt))
    total = sum(q for _, q in buy) + sum(q for _, q in sell)
    return total % MOD

JavaScript

var getNumberOfBacklogOrders = function(orders) {
    var MOD = 1000000007;
    var buy = [], sell = [];
    for (var i = 0; i < orders.length; i++) {
        var price = orders[i][0], type = orders[i][2];
        var amt = orders[i][1];
        var k, best;
        if (type === 0) {
            while (amt > 0 && sell.length > 0) {
                best = 0;
                for (k = 1; k < sell.length; k++) if (sell[k][0] < sell[best][0]) best = k;
                if (sell[best][0] > price) break;
                var take = Math.min(amt, sell[best][1]);
                amt -= take;
                sell[best][1] -= take;
                if (sell[best][1] === 0) sell.splice(best, 1);
            }
            if (amt > 0) buy.push([price, amt]);
        } else {
            while (amt > 0 && buy.length > 0) {
                best = 0;
                for (k = 1; k < buy.length; k++) if (buy[k][0] > buy[best][0]) best = k;
                if (buy[best][0] < price) break;
                var take2 = Math.min(amt, buy[best][1]);
                amt -= take2;
                buy[best][1] -= take2;
                if (buy[best][1] === 0) buy.splice(best, 1);
            }
            if (amt > 0) sell.push([price, amt]);
        }
    }
    var total = 0;
    for (i = 0; i < buy.length; i++) total = (total + buy[i][1]) % MOD;
    for (i = 0; i < sell.length; i++) total = (total + sell[i][1]) % MOD;
    return total;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue