We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number of Orders in the Backlog

Difficulty: Medium

Problem Description

You are given a 2D integer array orders, where each orders[i] = [price_i, amount_i, orderType_i] denotes that amount_i orders have been placed of type orderType_i at the 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.

There is a backlog that consists of orders that have not been executed. When an order is placed, buy and sell orders can match based on their prices. The task is to return the total amount of orders in the backlog after placing all the orders from the input, modulo 10^9 + 7.

Key Insights

  • Buy orders can only be matched with sell orders if the price of the sell order is less than or equal to the price of the buy order.
  • Sell orders can only be matched with buy orders if the price of the buy order is greater than or equal to the price of the sell order.
  • We need to keep track of both buy and sell orders in a manner that allows us to efficiently match them.
  • A min-heap can be used for sell orders to quickly access the lowest priced sell order.
  • A max-heap can be used for buy orders to quickly access the highest priced buy order.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of orders, because each insertion and removal in a heap takes O(log n) time. Space Complexity: O(n), as we may need to store all orders in the backlog.

Solution

To solve the problem, we utilize two heaps: a min-heap for sell orders and a max-heap for buy orders. As we process each order:

  1. For a buy order, we check the min-heap of sell orders. If the sell order's price is less than or equal to the buy order's price, we match them and reduce the order amounts accordingly. If not, we add the buy order to the max-heap.
  2. For a sell order, we check the max-heap of buy orders. If the buy order's price is greater than or equal to the sell order's price, we match them and reduce the order amounts. If not, we add the sell order to the min-heap.
  3. Finally, we sum up the remaining amounts in both heaps to determine the total backlog.

Code Solutions

import heapq

def getNumberOfBacklogOrders(orders):
    MOD = 10**9 + 7
    buy_heap = []  # max-heap for buy orders
    sell_heap = []  # min-heap for sell orders
    
    for price, amount, orderType in orders:
        if orderType == 0:  # buy order
            while amount > 0 and sell_heap and sell_heap[0][0] <= price:
                sell_price, sell_amount = heapq.heappop(sell_heap)
                if sell_amount > amount:
                    sell_amount -= amount
                    amount = 0
                    heapq.heappush(sell_heap, (sell_price, sell_amount))
                else:
                    amount -= sell_amount
            if amount > 0:
                heapq.heappush(buy_heap, (-price, amount))  # push negative price for max-heap
        else:  # sell order
            while amount > 0 and buy_heap and -buy_heap[0][0] >= price:
                buy_price, buy_amount = heapq.heappop(buy_heap)
                if buy_amount > amount:
                    buy_amount -= amount
                    amount = 0
                    heapq.heappush(buy_heap, (buy_price, buy_amount))
                else:
                    amount -= buy_amount
            if amount > 0:
                heapq.heappush(sell_heap, (price, amount))

    total_backlog = sum(amount for _, amount in buy_heap) + sum(amount for _, amount in sell_heap)
    return total_backlog % MOD
← Back to All Questions