SimuVedaAlgorithms Lab Open in the lab

Patterns / Intermediate

Monotonic Stack Visualizer

The stack holds values still waiting for an answer. A bigger value pops everything smaller than it and becomes their answer.

Start the Monotonic Stack simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. The stack holds values still waiting for a bigger value on their right. [4, 5, 2, 10, 8, 3, 7]
  2. Look at 4.
  3. Push 4. It waits for something bigger.
  4. Look at 5.
  5. 4 < 5, so 5 is the next greater value for 4. Pop it.
  6. Push 5. It waits for something bigger.
  7. Look at 2.
  8. Push 2. It waits for something bigger.
  9. Look at 10.
  10. 2 < 10, so 10 is the next greater value for 2. Pop it.
  11. 5 < 10, so 10 is the next greater value for 5. Pop it.
  12. Push 10. It waits for something bigger.
  13. Look at 8.
  14. Push 8. It waits for something bigger.
  15. Look at 3.
  16. Push 3. It waits for something bigger.
  17. Look at 7.
  18. 3 < 7, so 7 is the next greater value for 3. Pop it.
  19. Push 7. It waits for something bigger.
  20. Done. Values still on the stack have nothing bigger after them, so they stay -1.

Try it with your own input →

Monotonic stack in Java, Python, C++, C and JavaScript

int[] nextGreater(int[] a) {
  int[] res = new int[a.length];
  Arrays.fill(res, -1);
  Deque<Integer> st = new ArrayDeque<>();
  for (int i = 0; i < a.length; i++) {
    while (!st.isEmpty() && a[st.peek()] < a[i]) {
      res[st.pop()] = a[i];
    }
    st.push(i);
  }
  return res;
}
def next_greater(a):
    res = [-1] * len(a)
    st = []
    for i in range(len(a)):
        while st and a[st[-1]] < a[i]:
            res[st.pop()] = a[i]
        st.append(i)
    return res
vector<int> nextGreater(const vector<int>& a) {
  vector<int> res(a.size(), -1);
  stack<int> st;
  for (int i = 0; i < (int)a.size(); i++) {
    while (!st.empty() && a[st.top()] < a[i]) {
      res[st.top()] = a[i]; st.pop();
    }
    st.push(i);
  }
  return res;
}
#include <stdlib.h>

void nextGreater(int a[], int n, int res[]) {
  for (int i = 0; i < n; i++) res[i] = -1;
  int *st = malloc(n * sizeof(int)), top = 0;
  for (int i = 0; i < n; i++) {
    while (top > 0 && a[st[top - 1]] < a[i]) {
      res[st[--top]] = a[i];
    }
    st[top++] = i;
  }
  free(st);
}
function nextGreater(a) {
  const res = new Array(a.length).fill(-1);
  const st = [];
  for (let i = 0; i < a.length; i++) {
    while (st.length > 0 && a[st[st.length - 1]] < a[i]) {
      res[st.pop()] = a[i];
    }
    st.push(i);
  }
  return res;
}

In an interview

Next Greater Element (LeetCode 496). Same pattern: 739 Daily Temperatures, 84 Largest Rectangle in Histogram.

Each value is pushed once and popped once, so it is O(n) even with the inner while loop.

More patterns