LeetCode Solutions Blog

Number of Orders in the Backlog

Number: 1928

Difficulty: Medium

Paid? No

Companies: Robinhood

Problem Description

You are given an array of orders where each order is represented as [price, amount, orderType]. A buy order (orderType = 0) can match with a sell order (orderType = 1) in the backlog if the buy price is at least the sell price. Conversely, a sell order may match with a buy order if the buy order's price is at least the sell order's price. Process all orders in sequence, match orders when possible, and finally count the remaining orders in the backlog modulo 10^9 + 7.

Key Insights

Use two heaps: a max-heap for buy orders and a min-heap for sell orders.
For a buy order, match with the lowest-priced sell orders (min-heap) as long as the sell price is <= buy price.
For a sell order, match with the highest-priced buy orders (max-heap) as long as the buy price is >= sell price.
Update the order amounts accordingly during matching and push back any remaining amounts.
Use modulo arithmetic for large sums.

Space and Time Complexity

Time Complexity: O(n log n) due to inserting and polling from heaps for each order. Space Complexity: O(n) for the storage of orders in the heaps.

Solution

The solution maintains two heaps:

A max-heap for buy orders (using negative prices in languages without a built-in max-heap) to quickly access the order with the highest price.
A min-heap for sell orders to quickly access the order with the lowest price.

For each new order:

If it is a buy order, continually match it with the smallest priced sell order (if sell price ≤ buy price). Decrease the amounts accordingly. If any buy order amount remains after no match is possible, add it to the max-heap.
If it is a sell order, continually match it with the highest priced buy order (if buy price ≥ sell price). Adjust amounts, and if any sell order amount remains after matching, add it to the min-heap.

After processing all orders, sum the amounts in both heaps and return the result modulo (10^9 + 7).

Code Solutions

import heapq

MOD = 10**9 + 7

def getNumberOfBacklogOrders(orders):
    # Max-heap for buy orders (store negative price to simulate max heap)
    buy_heap = []
    # Min-heap for sell orders
    sell_heap = []
    
    for price, amount, orderType in orders:
        # Buy order
        if orderType == 0:
            # Match with sell orders (min-heap) with price <= current buy price
            while amount > 0 and sell_heap and sell_heap[0][0] <= price:
                sell_price, sell_amount = heapq.heappop(sell_heap)
                # Determine how many orders can be matched
                matched = min(amount, sell_amount)
                amount -= matched
                sell_amount -= matched
                
                # If there are remaining sell orders, push back into the min-heap
                if sell_amount > 0:
                    heapq.heappush(sell_heap, (sell_price, sell_amount))
            # If buy order still has remaining amount after matching
            if amount > 0:
                heapq.heappush(buy_heap, (-price, amount))
                
        # Sell order    
        else:
            # Match with buy orders (max-heap, hence negative prices) with price >= current sell price
            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 there are remaining buy orders, push back into max-heap
                if buy_amount > 0:
                    heapq.heappush(buy_heap, (buy_price, buy_amount))
            # If sell order still has remaining amount after matching
            if amount > 0:
                heapq.heappush(sell_heap, (price, amount))
    
    # Sum up the amounts in both heaps for the backlog count
    backlog = sum(amount for _, amount in buy_heap) + sum(amount for _, amount in sell_heap)
    return backlog % MOD

# Example usage:
orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
print(getNumberOfBacklogOrders(orders))