Explain Monotonic Stack. What problems does it solve?

0-2 years experience

1. 1We are building a simple weather dashboard. Given an array of daily temperatures, how would you efficiently find how many days you have to wait for a warmer day for each day? Walk me through how you'd track this without using a nested loop.
2. 2Imagine you have an array of building heights. You want to find the first building to the right that is taller than the current one. If we use a stack to keep track of the indices, what exactly happens to the stack when we encounter a building that is shorter than the one at the top of the stack?

2-5 years experience

1. 1We have a feature in our monitoring dashboard that renders a histogram of server response times, and we need to find the largest rectangular area of peak activity. A junior dev wrote a nested loop solution that is timing out on large metrics payloads. How would you refactor this to run in linear time, and how do you handle the edge case where the bars are strictly decreasing?
2. 2We're implementing a text editor feature that formats nested markdown-like custom tags. A colleague used a standard stack, but we're seeing memory leaks and slow performance when processing deeply nested, repetitive structures. How could we use a monotonic property to prune redundant elements early, and what are the trade-offs of doing so?

5-8 years experience

1. 1We are designing a real-time sliding window analytics engine that processes a high-throughput stream of IoT sensor readings. We need to calculate the maximum value in every sliding window of size K. How would you design the in-memory data structure to support this with O(1) amortized time per incoming reading, and how do you handle out-of-order data arrivals?
2. 2In a high-frequency trading system, we need to calculate the 'next price spike' for millions of ticks per second. Memory allocation is our primary bottleneck. If we use a monotonic stack pattern, how would you implement it to avoid garbage collection overhead or dynamic array resizing in a language like Java or Go?

8+ years experience

1. 1Our data ingestion pipeline uses a complex, custom-built monotonic queue/stack library to calculate rolling metrics. Newer team members are struggling to maintain this code, leading to subtle off-by-one bugs during feature additions. How would you evaluate whether to keep this highly optimized O(N) custom component versus refactoring it to a simpler, more readable O(N log N) or database-level aggregation, considering long-term maintenance costs?
2. 2We are migrating a legacy batch-processing system to a real-time event-driven architecture. The legacy system used a monotonic stack over static daily files to find trend reversals. In a distributed, partitioned stream (like Kafka), how do we maintain this monotonic state across partition rebalances and out-of-order event delivery without introducing massive state-store bottlenecks?