Merge two price ladders, summing size on equal prices

Question

You have two order-book ladders for the same side, each a list of (price, size) sorted ascending by price with distinct prices. Merge them into one ladder sorted by price, and where both ladders quote the same price, combine them into a single level whose size is the sum.

a = [(99,10), (100,5), (101,8)]
b = [(100,7), (101,2), (102,4)]
-> [(99,10), (100,12), (101,10), (102,4)]

Target $O(m + n)$ time.

Accepted Answer

It is the standard two-pointer merge with one extra branch: when the two front prices are equal, emit a single level carrying the summed size and advance both pointers. Otherwise emit the cheaper price and advance that side. Tracing the example: 99 < 100 emits (99,10); the two 100 levels merge into (100,12); the two 101 levels merge into (101,10); ladder a is now empty, so the leftover (102,4) from b is attached wholesale. Result [(99,10), (100,12), (101,10), (102,4)]. Because the inputs are sorted and prices within each ladder are distinct, a matched price is fully consumed by summing once, …

Merge two price ladders, summing size on equal prices

Your answer

More Coding questions