How hard is LeetCode 1801. Number of Orders in the Backlog?

LeetCode 1801. Number of Orders in the Backlog is rated Medium on LeetCode.

What is the time complexity of LeetCode 1801. Number of Orders in the Backlog?

The Python solution on this page runs in O(n \times \log n).

What is the space complexity of LeetCode 1801. Number of Orders in the Backlog?

The Python solution on this page uses O(n) auxiliary space.

What topics does LeetCode 1801. Number of Orders in the Backlog cover?

LeetCode 1801. Number of Orders in the Backlog is tagged Array, Simulation and Heap (Priority Queue) on LeetCode.

Number of Orders in the Backlog — LeetCode 1801 Python Solution

MediumArraySimulationHeap (Priority Queue)

Problem: #1801
Pattern: Heap / Priority Queue
Reading time: 6 min
Source: leetcode.com

The problem

You are given a 2D integer array orders, where each orders[i] = [pricei, amounti, orderTypei] denotes that amounti orders have been placed of type orderTypei at the price pricei. The orderTypei is: 0 if it is a batch of buy orders, or 1 if it is a batch of sell orders.

Example

Input: orders = [[10,5,0],[15,2,1],[25,1,1],[30,4,0]]
Output: 6
Explanation: Here is what happens with the orders:

Python solution

Python

class Solution:
    def getNumberOfBacklogOrders(self, orders: List[List[int]]) -> int:
        buy, sell = [], []
        for p, a, t in orders:
            if t == 0:
                while a and sell and sell[0][0] <= p:
                    x, y = heappop(sell)
                    if a >= y:
                        a -= y
                    else:
                        heappush(sell, (x, y - a))
                        a = 0
                if a:
                    heappush(buy, (-p, a))
            else:
                while a and buy and -buy[0][0] >= p:
                    x, y = heappop(buy)
                    if a >= y:
                        a -= y
                    else:
                        heappush(buy, (x, y - a))
                        a = 0
                if a:
                    heappush(sell, (p, a))
        mod = 10**9 + 7
        return sum(v[1] for v in buy + sell) % mod

Complexity

Measure	Complexity
Time	O(n \times \log n)
Space	O(n) auxiliary

Pattern: Heap / Priority Queue

Keep only the best k elements, or always pull the smallest, in log time. LeetCode 1801. Number of Orders in the Backlog is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Heap (Priority Queue).

The heap / priority queue guide has the Python template for the pattern and the 163 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1801. Number of Orders in the Backlog?: LeetCode 1801. Number of Orders in the Backlog is rated Medium on LeetCode.
What is the time complexity of LeetCode 1801. Number of Orders in the Backlog?: The Python solution on this page runs in O(n \times \log n).
What is the space complexity of LeetCode 1801. Number of Orders in the Backlog?: The Python solution on this page uses O(n) auxiliary space.
What topics does LeetCode 1801. Number of Orders in the Backlog cover?: LeetCode 1801. Number of Orders in the Backlog is tagged Array, Simulation and Heap (Priority Queue) on LeetCode.