Number of Orders in the Backlog

Medium
965.

Number of Orders in the Backlog

Number of Orders in the Backlog is a medium coding problem on arrays, simulation and heap, asked in Amazon, Google and Morgan Stanley interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} orders
 * @return {number}
 */
var getNumberOfBacklogOrders = function(orders) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Orders in the Backlog — Problem & Solution

Number of Orders in the Backlog solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Orders in the Backlog is a medium coding problem on arrays, simulation and heap, asked in Amazon, Google and Morgan Stanley interviews.

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

Hints for Number of Orders in the Backlog

  1. Hint 1

    Keep two backlogs: buys in a max-heap by price, sells in a min-heap by price.

  2. Hint 2

    An incoming order matches repeatedly against the opposite heap's top while the prices allow.

  3. Hint 3

    Group identical prices into one heap entry with a quantity, or 10^9 single orders will not fit.

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

  1. For a buy at price, while the cheapest sell is at most price, cancel min(amount, thatEntry) from both.
  2. For a sell, do the mirror image against the most expensive buy.
  3. Push whatever is left of the incoming order onto its own heap.
  4. 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

Java

public static int getNumberOfBacklogOrders(int[][] orders) {
    final long MOD = 1000000007L;
    PriorityQueue<long[]> buy = new PriorityQueue<>((a, b) -> Long.compare(b[0], a[0]));
    PriorityQueue<long[]> sell = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
    for (int[] o : orders) {
        long price = o[0], amt = o[1];
        if (o[2] == 0) {
            while (amt > 0 && !sell.isEmpty() && sell.peek()[0] <= price) {
                long[] top = sell.poll();
                long take = Math.min(amt, top[1]);
                amt -= take;
                top[1] -= take;
                if (top[1] > 0) sell.add(top);
            }
            if (amt > 0) buy.add(new long[] { price, amt });
        } else {
            while (amt > 0 && !buy.isEmpty() && buy.peek()[0] >= price) {
                long[] top = buy.poll();
                long take = Math.min(amt, top[1]);
                amt -= take;
                top[1] -= take;
                if (top[1] > 0) buy.add(top);
            }
            if (amt > 0) sell.add(new long[] { price, amt });
        }
    }
    long total = 0;
    for (long[] e : buy) total = (total + e[1]) % MOD;
    for (long[] e : sell) total = (total + e[1]) % MOD;
    return (int) total;
}

C++

int getNumberOfBacklogOrders(vector<vector<int>>& orders) {
    const long long MOD = 1000000007;
    priority_queue<pair<long long,long long>> buy;
    priority_queue<pair<long long,long long>, vector<pair<long long,long long>>, greater<pair<long long,long long>>> sell;
    for (auto& o : orders) {
        long long price = o[0], amt = o[1];
        if (o[2] == 0) {
            while (amt > 0 && !sell.empty() && sell.top().first <= price) {
                auto top = sell.top();
                sell.pop();
                long long take = min(amt, top.second);
                amt -= take;
                top.second -= take;
                if (top.second > 0) sell.push(top);
            }
            if (amt > 0) buy.push({ price, amt });
        } else {
            while (amt > 0 && !buy.empty() && buy.top().first >= price) {
                auto top = buy.top();
                buy.pop();
                long long take = min(amt, top.second);
                amt -= take;
                top.second -= take;
                if (top.second > 0) buy.push(top);
            }
            if (amt > 0) sell.push({ price, amt });
        }
    }
    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;
}

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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Heaps and Priority Queues