Bid-Ask Spread After Each Quote
Problem
A quote board receives quotes as ("buy", price) or ("sell", price). Nothing trades on this board, so every quote stays. After each quote, report the spread: the lowest sell price minus the highest buy price. When either side has no quotes yet, report None. Return the list of reports.
Examples
Input: quotes = [("buy", 100), ("sell", 105), ("buy", 102), ("sell", 104), ("buy", 99)]
Output: [None, 5, 3, 2, 2]
Why: the best buy climbs to 102 and the best sell drops to 104, and the low buy at 99 changes nothingInput: quotes = [("sell", 50), ("sell", 40)]
Output: [None, None]
Why: nobody has quoted a buy price yetInput: quotes = [("buy", 12), ("sell", 10)]
Output: [None, -2]
Why: edge case, nothing trades here, so a crossed board simply shows a negative spreadHints
0 / 3
Only two prices matter after each quote: the highest buy and the lowest sell. Rescanning every quote each time is quadratic.
The buy side needs its maximum on demand and the sell side needs its minimum on demand, while both sides keep growing. One heap per side gives each answer in constant time.
Push buy prices onto a max-heap and sell prices onto a min-heap. After each quote, if both heaps are non-empty, report the sell heap's top minus the buy heap's top, otherwise report None.
Solution
The board is two halves with a boundary between them, which is the shape the two-heaps pattern handles: a max-heap for the buy side, so the highest buy is on top, and a min-heap for the sell side, so the lowest sell is on top. Each quote is one push onto its own side, and the spread reads only the two tops. Python's heapq is a min-heap, so buy prices are stored negated, which turns the difference into a sum of the two tops. Each quote costs O(log n), so time is O(n log n) and space is O(n).
import heapq
def spreads(quotes):
bids, asks = [], [] # bids: max-heap of negated prices, asks: min-heap
reports = []
for side, price in quotes:
if side == "buy":
heapq.heappush(bids, -price)
else:
heapq.heappush(asks, price)
# lowest sell minus highest buy; bids are stored negated
reports.append(asks[0] + bids[0] if bids and asks else None)
return reports
print(spreads([("buy", 100), ("sell", 105), ("buy", 102), ("sell", 104), ("buy", 99)])) # -> [None, 5, 3, 2, 2]
print(spreads([("sell", 50), ("sell", 40)])) # -> [None, None]
print(spreads([("buy", 12), ("sell", 10)])) # -> [None, -2]Stuck on the idea rather than the code? Heap Basics covers it.