You are given a 2D integer array orders, where orders[i] = [price_i, amount_i, orderType_i] denotes that amount_i orders have been placed of type orderType_i at price price_i. The orderType_i is:

  • 0 if it is a batch of buy orders, or
  • 1 if it is a batch of sell orders.

Note that orders[i] represents a batch of amount_i independent orders with the same price and type. All orders represented by orders[i] will be placed before all orders represented by orders[i+1] for all valid i.

There is a backlog that consists of orders that have not been executed. The backlog is initially empty. When an order is placed, the following happens:

  • If the order is a buy order, you look at the sell order with the smallest price in the backlog. If that sell order’s price is smaller than or equal to the current buy order’s price, they will match and be executed, and that sell order will be removed from the backlog. Else, the buy order is added to the backlog.
  • Vice versa, if the order is a sell order, you look at the buy order with the largest price in the backlog. If that buy order’s price is larger than or equal to the current sell order’s price, they will match and be executed, and that buy order will be removed from the backlog. Else, the sell order is added to the backlog.

Return the total amount of orders in the backlog after placing all the orders from the input. Since the number can be large, return it modulo 10^9 + 7.

Examples

Example 1:

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6
Explanation: Here is what happens with the orders:
- 5 orders of type buy with price 10 are placed. There are no sell orders in the backlog, so the 5 orders are added to the backlog.
- 2 orders of type sell with price 15 are placed. There are no buy orders in the backlog with price >= 15, so the 2 orders are added to the backlog.
- 1 order of type sell with price 25 is placed. There are no buy orders in the backlog with price >= 25, so it is added to the backlog.
- 4 orders of type buy with price 30 are placed. The first sell order with price 15 is matched and removed, and 4 is reduced by 1 to 3. The second sell order with price 15 is matched and removed, and 3 is reduced by 2 to 1. The third sell order with price 25 is matched and removed, and 1 is reduced by 1 to 0. The 4 buy orders with price 30 are now added to the backlog.
Finally, the backlog has 5 + 1 = 6 orders. So we return 6.

Example 2:

Input: orders = [[7,1000000000,1],[15,3,0],[5,999999995,0],[5,1,1]]
Output: 999999984
Explanation: Here is what happens with the orders:
- 10^9 orders of type sell with price 7 are placed. There are no buy orders, so the 10^9 orders are added to the backlog.
- 3 orders of type buy with price 15 are placed. They are matched with the 3 sell orders with the smallest price, which is 7, and these 3 sell orders are removed from the backlog.
- 999999995 orders of type buy with price 5 are placed. The sell order with price 7 should be matched, but since the buy order price is 5 < 7, it is not matched. Instead, 999999995 orders are added to the backlog.
- 1 order of type sell with price 5 is placed. This sell order is matched with a buy order of price 5, so 1 buy order is removed, and 999999994 orders remain in the backlog.
Finally, the backlog has (10^9 - 3) + 999999994 = 1999999991 orders. So we return 1999999991 mod 10^9 + 7 = 999999984.

Constraints

  • 1 <= orders.length <= 10^5
  • orders[i].length == 3
  • 1 <= price_i, amount_i <= 10^9
  • orderType_i is either 0 or 1.

Thinking Process

  1. Heap Selection:
    • Max heap for buy orders (want highest price)
    • Min heap for sell orders (want lowest price)
    • Always match with best available price
  • Heap gives fast access to min/max without full sorting.
  • Size-k heap handles Top-K in O(n log k).
  • Lazy deletion when elements leave the heap before removal.
Binary heap 1 3 2 parent ≤ children (min-heap)

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Min/max heap (this problem) O(n log k) O(k) Top-K, streaming median
Two heaps O(n log n) O(n) Median from data stream
Heap + lazy deletion O(n log n) O(n) Delayed removal
Priority-driven search O(n log n) O(n) Dijkstra, best-first expansion

Solution

import heapq

class Solution:
    def getNumberOfBacklogOrders(self, orders):
        MOD = 10**9 + 7
        
        buy = []   # max heap (use negative price)
        sell = []  # min heap
        
        for o in orders:
            price, amount, type = o[0], o[1], o[2]
            
            if type == 0:
                while amount > 0 and sell and sell[0][0] <= price:
                    sellPrice, sellAmount = heapq.heappop(sell)
                    matched = min(amount, sellAmount)
                    amount -= matched
                    sellAmount -= matched
                    
                    if sellAmount > 0:
                        heapq.heappush(sell, (sellPrice, sellAmount))
                
                if amount > 0:
                    heapq.heappush(buy, (-price, amount))
            
            else:
                while amount > 0 and buy and -buy[0][0] >= price:
                    buyPrice, buyAmount = heapq.heappop(buy)
                    buyPrice = -buyPrice
                    matched = min(amount, buyAmount)
                    amount -= matched
                    buyAmount -= matched
                    
                    if buyAmount > 0:
                        heapq.heappush(buy, (-buyPrice, buyAmount))
                
                if amount > 0:
                    heapq.heappush(sell, (price, amount))
        
        rtn = 0
        
        while buy:
            rtn = (rtn + buy[0][1]) % MOD
            heapq.heappop(buy)
        
        while sell:
            rtn = (rtn + sell[0][1]) % MOD
            heapq.heappop(sell)
        
        return rtn

Solution Explanation

Approach: Min/max heap (this problem)

Key idea: 1. Heap Selection:

How the code works:

  1. Heap Selection:
    • Max heap for buy orders (want highest price)
    • Min heap for sell orders (want lowest price)
    • Always match with best available price
    • Heap gives fast access to min/max without full sorting.
    • Size-k heap handles Top-K in O(n log k).

Walkthrough — input orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]], expected output 6:

Here is what happens with the orders:

  • 5 orders of type buy with price 10 are placed. There are no sell orders in the backlog, so the 5 orders are added to the backlog.
  • 2 orders of type sell with price 15 are placed. There are no buy orders in the backlog with price >= 15, so the 2 orders are added to the backlog.
  • 1 order of type sell with price 25 is placed. There are no buy orders in the backlog with price >= 25, so it is added to the backlog.
  • 4 orders of type buy with price 30 are placed. The first sell order with price 15 is matched and removed, and 4 is reduced by 1 to 3. The second sell order with price 15 is matched and removed, and 3 is reduced by 2 to 1. The third sell order with price 25 is matched and removed, and 1 is reduced by 1 to 0. The 4 buy orders with price 30 are now added to the backlog. Finally, the backlog has 5 + 1 = 6 orders. So we return 6.

    Common Mistakes

  1. No matches: All orders added to backlog
    • orders = [[10,5,0],[20,3,1]] → buy: 5, sell: 3, total: 8
  2. Complete matching: All orders matched
    • orders = [[10,5,0],[10,5,1]] → buy: 0, sell: 0, total: 0
  3. Partial matching: Some orders partially matched
    • orders = [[10,5,0],[8,3,1]] → buy: 2, sell: 0, total: 2
  4. Large amounts: Handle modulo correctly
    • Example 2 shows handling of 10^9 amounts
  5. Empty backlog: No orders remain
    • All orders matched perfectly
  6. Wrong heap type: Using min heap for buy orders or max heap for sell orders
  7. Incorrect matching condition:
    • Buy matches when buyPrice >= sellPrice (not >)
    • Sell matches when sellPrice <= buyPrice (not <)
  8. Not handling partial matches: Forgetting to push back remaining amounts
  9. Modulo overflow: Not applying modulo during accumulation
  10. Empty heap access: Not checking if heap is empty before accessing top
  11. Integer overflow: Not using long long for result accumulation

Key Takeaways

  1. Heap Selection:
    • Max heap for buy orders (want highest price)
    • Min heap for sell orders (want lowest price)
  2. Matching Strategy:
    • Always match with best available price
    • Partial matching is allowed
  3. Order Processing:
    • Process orders sequentially
    • Match greedily until no more matches possible
  4. Modulo Arithmetic:
    • Use modulo when summing to prevent overflow
    • Apply modulo at each addition step

References

Template Reference