Design a stack that reports its range

Question

You are buffering the ticks currently in a short window and want a cheap volatility gauge: the range, highest tick minus lowest tick, of whatever is in the buffer right now. As ticks are pushed and popped, get_range must stay $O(1)$ .

s = RangeStack()
s.push(4); s.push(9); s.push(4); s.push(1)
s.get_range() -> 8        # max 9, min 1
s.pop()                   # removes 1
s.get_range() -> 5        # max 9, min 4

Design push, pop, top, and get_range with every operation in $O(1)$ .

Accepted Answer

Range needs both extremes, so carry two auxiliary stacks (or one stack of pairs): a running minimum and a running maximum, each snapshotting its aggregate at every depth. getrange subtracts the two tops. Popping rewinds both extremes automatically because each level stored the min and max as of that depth. Tracing: after pushing 4, 9, 4, 1 the min stack is [4, 4, 4, 1] and the max stack is [4, 9, 9, 9], so getrange is 9 - 1 = 8. Pop the 1: mins [4, 4, 4], maxs [4, 9, 9], range 9 - 4 = 5. Correct. All operations O(1); space O(n) for the two side stacks. Takeaway. A derived quantity like range …

Design a stack that reports its range

Your answer

More Coding questions