Largest solid block in an order-book depth chart
Asked at Optiver, Hudson River Trading
Resting depth at consecutive price levels forms a histogram (each bar is a non-negative height). Find the area of the largest axis-aligned rectangle that fits entirely under the bars, a proxy for the biggest contiguous block of liquidity you could sweep at a uniform depth.
depth = [2, 1, 5, 6, 2, 3]
-> 10 # levels 5 and 6, height 5, width 2
Return the maximum rectangle area under the histogram in O(n) time.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.