Max Stack with popMax() – interesting discussion from a recent interview

I had a coding interview recently (before onsite stage) and one of the questions was about implementing a Max Stack. Most people know the standard solution: You maintain another stack that keeps t

I had a coding interview recently (before onsite stage) and one of the questions was about implementing a Max Stack. Most people know the standard solution: You maintain another stack that keeps track of the current maximum at every push. But the twist here was that the stack also needed to support popMax() — remove and return the maximum element currently in the stack. So we discussed two approaches. 1. Naive approach One approach is: * Pop elements from the stack into a temporary stack until the max element is found * Remove that max element * Push everything back This works but the complexity of popMax() becomes O(n). 2. Optimized approach The approach I suggested was: * Maintain the stack as a doubly linked list * Maintain a TreeMap (or ordered map) from value → list of nodes This allows: * push → add node to DLL and insert into TreeMap * pop → remove from DLL and update TreeMap * peekMax → get lastKey() from TreeMap * popMax → get max value from TreeMap, remove the most recent node from DLL With this structure: * Stack operations remain O(1) * Finding the max becomes O(log n) via the ordered map It was a nice discussion because the interviewer was more interested in how the data structures interact rather than just coding the stack. Note: The content above reflects my interview discussion. I used ChatGPT to help rephrase it for clarity. EDIT : Mar 9th 2026 10:22 PST Want to share one of the approach since we had lot of healthy discussions in the comments <a href="https://www.interviewpickle.com/ds-algo/beyond-75/min-stack-v2>