MinStack, MaxStack and Streaming Median

Three linked structures in a single MLE round: `MinStack` with O(1) min, `MaxStack`, and a streaming-median follow-up that pushes you to two heaps — then asks how to retrofit `MaxStack` to maintain the running median. Requirements Three sub-problems delivered in escalating difficulty: MinStack: standard stack with push, pop, top, plus getMin in O(1) time. MaxStack: same but with getMax in O(1) (typical LC-extension is also peekMax and popMax). Streaming Median: data flows in one value at a time; after each insertion, return the current running median in O(log n). Composite follow-up: how would you modify your MaxStack implementation if you also need the running median maintained? class MinStack: ... class MaxStack: ... class MedianFinder: def addNum(self, num: int) -> None: ... def findMedian(self) -> float: ... Notes MinStack is solved with a paired stack: each entry is (value, current_min), or with a secondary stack that only stores running minimums. MaxStack is symmetric; if popMax is required, the O(1) invariant breaks down and the standard answer is "two stacks + lazy rebalance" or "tree-based ordered set + linked list" for O(log n). Streaming median is the two-heap pattern: a max-heap for the lower half, min-heap for the upper half. Keep sizes balanced within 1; median is the top of the larger heap, or the average of the two tops. For the composite "MaxStack + running median" follow-up, the cleanest answer is to keep your MaxStack as-is for the stack interface and run a side two-heap structure that observes every push/pop event. Discuss the cost of removing arbitrary elements from a heap (O(log n) with a hashmap-indexed lazy-deletion heap, or O(n) with naive rebuild). Common bug: in the two-heap median, forgetting to negate values for Python's heapq (which is min-heap only) when used as a max-heap. Preparation Code MinStack with both the paired-stack and secondary-stack approaches; be able to switch between them. Drill the two-heap median template until you can write it without thinking, including the rebalance rules. Practice the lazy-deletion heap pattern — heap plus to_delete counter dict — for the composite follow-up. Walk through a 5-element stream by hand, naming the median at every step, to make sure rebalancing is right.