Monotonic Stack

A street has six buildings in a row, with heights of 5, 3, 1, 4, 6 and 2 floors from west to east. For each building, you want the first taller building to its east, the one that blocks its view of the sunrise. Building 1 (3 floors) is blocked by building 3 (4 floors). Building 4 (6 floors) is blocked by nothing.

The obvious way is to start at each building and walk east until you hit a taller one. That is O(n²) in the worst case: on a street that gets steadily shorter, every walk goes to the very end. With 100,000 buildings that is about 5 billion steps. A stack does it in one pass.

#The idea: a line of buildings still waiting

Walk from west to east. Keep a stack of the buildings that have not found their answer yet. When a new building arrives, look at the top of the stack. If the new building is taller, it is the answer for that waiting building, so pop it and record the answer. Keep popping while the new building is taller than the top. Then push the new building: it now waits for its own answer.

Anything shorter than the new building is popped before it is pushed. So the heights on the stack always go down from bottom to top. A stack whose items stay in sorted order like this is called a monotonic stack, here a decreasing one.

Popping is safe. The popped building has found its answer, and the answer can only be the first taller building, which is this one. It will never need to be looked at again.

answer = [-1] * nfor i in 0 .. n - 1:  while stack not empty and h[top] < h[i]:    answer[pop()] = i  push(i)return answer

#The code

// For each building, the index of the first taller one to its right, or -1.
function nextTaller(heights) {
  const answer = new Array(heights.length).fill(-1);
  const stack = []; // indexes still waiting; heights decrease bottom to top
  for (let i = 0; i < heights.length; i++) {
    while (stack.length > 0 && heights[stack[stack.length - 1]] < heights[i]) {
      answer[stack.pop()] = i; // i is the first taller one for the top
    }
    stack.push(i); // i waits for its own answer
  }
  return answer; // anything still waiting keeps -1
}
 
nextTaller([5, 3, 1, 4, 6, 2]); // [4, 3, 3, 4, -1, -1]

# For each building, the index of the first taller one to its right, or -1.
def next_taller(heights):
    answer = [-1] * len(heights)
    stack = []  # indexes still waiting; heights decrease bottom to top
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] < h:
            answer[stack.pop()] = i  # i is the first taller one for the top
        stack.append(i)  # i waits for its own answer
    return answer  # anything still waiting keeps -1
 
next_taller([5, 3, 1, 4, 6, 2])  # [4, 3, 3, 4, -1, -1]

The stack stores indexes, not heights: you need the index to write into answer, and you can look up the height from it. The index also tells you how far away the answer is: i - index.

The while inside the for looks like O(n²). Count pops instead of loop runs: a pop removes an index for good, and only n indexes are ever pushed, so all the while loops together pop at most n times. This is the same "count the total moves" argument as in Two Pointers.

#Four questions, one pattern

Flip the comparison and you get the other variants. For "next smaller", pop while the top is bigger than the new item; the stack is then increasing. For "previous taller" or "previous smaller", read the answer from the other side: after the popping stops, whatever is left on top is the nearest earlier item that survived, so it is the answer for the new item. Here you also pop equal items, so that what is left on top is strictly taller or strictly smaller.

#The deque version: the biggest in every window

A close cousin asks for the largest value in every stretch of k items next to each other. For [4, 2, 12, 3, 8, 7, 1] and k = 3, the windows are [4, 2, 12], [2, 12, 3] and so on, and the answers are 12, 12, 12, 8, 8.

Keep a decreasing stack of indexes exactly as before: a new item pops every item that is not bigger than it off the back, because such an older item can never again be the biggest in any window that contains the new one. The biggest item in the window is then at the front. When the front's index slides out of the window, remove it from the front. Removing from both ends means a deque; the JavaScript version uses the head-index trick from that lesson.

function windowMax(nums, k) {
  const dq = []; // indexes; values decrease from front to back
  let head = 0;  // front of the deque
  const result = [];
  for (let i = 0; i < nums.length; i++) {
    if (head < dq.length && dq[head] <= i - k) head++; // front left the window
    while (head < dq.length && nums[dq[dq.length - 1]] <= nums[i]) dq.pop();
    dq.push(i);
    if (i >= k - 1) result.push(nums[dq[head]]); // front is the biggest
  }
  return result;
}
 
windowMax([4, 2, 12, 3, 8, 7, 1], 3); // [12, 12, 12, 8, 8]

from collections import deque
 
def window_max(nums, k):
    dq = deque()  # indexes; values decrease from front to back
    result = []
    for i, x in enumerate(nums):
        if dq and dq[0] <= i - k:
            dq.popleft()  # front left the window
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            result.append(nums[dq[0]])  # front is the biggest
    return result
 
window_max([4, 2, 12, 3, 8, 7, 1], 3)  # [12, 12, 12, 8, 8]

Each index enters the deque once and leaves at most once, from one end or the other, so this is O(n) too, against O(n·k) for scanning every window. The window itself slides as in Sliding Window.

#Common mistakes

#Check yourself

#What to practise next

Run nextTaller by hand on a falling street, [9, 7, 4, 2], and a rising one, [1, 3, 6, 8], to see the two extremes: a stack that only grows, and one that never holds more than one building. Then solve Waiting for a Bigger Wave with the stack and Freezer Warmest Stretch with the deque. The next module begins with Simple Sorts, where you put whole lists in order.