Number of orders in the backlog

November 20, 2022


Problem URL: Number of orders in the backlog

We will use two heaps to keep track of the buy and sell orders. The buy orders will be stored in a max heap and the sell orders will be stored in a min heap. We will also keep track of the total number of orders in the backlog.

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        sell, buy = [], []
        for p, a, t in orders:
            if t == 0:
                heapq.heappush(buy, [-p, a])
                heapq.heappush(sell, [p, a])

            while sell and buy and sell[0][0] <= -buy[0][0]:
                k = min(buy[0][1], sell[0][1])
                buy[0][1] -= k
                sell[0][1] -= k
                if buy[0][1] == 0: 
                if sell[0][1] == 0: 

        return sum(a for p, a in buy+sell) % (10**9+7)

Time complexity: O(nlog(n))
Space complexity: O(n)