practice · medium · from Stacks

Next Greater Element

time: O(n)
space: O(n)
tags: stacks · monotonic-stack

in the wild Find the next higher temperature reading in a sensor stream; find the next price peak in a tick-by-tick feed.

Monotonic stack · next greater element

…

speed step 0 / 0

Problem

Given an integer array nums, return an array answer such that answer[i] is the first element to the right of nums[i] that is greater than nums[i], or -1 if no such element exists.

Examples

nums = [2, 1, 2, 4, 3, 1] → [4, 2, 4, -1, -1, -1]
- 2 → next greater is 4
- 1 → next greater is 2
- 2 → next greater is 4
- 4 → nothing greater to the right
nums = [1, 2, 3, 4] → [2, 3, 4, -1]
nums = [4, 3, 2, 1] → [-1, -1, -1, -1]

Why this is the canonical monotonic-stack problem

Naïve: for each i, scan rightward until you find a bigger element. O(n²) worst case.

The trick is a monotonic decreasing stack — keep on the stack only the indices whose values are still "waiting" for a greater right-neighbor. Process the array left-to-right:

While nums[top] < nums[i], we've found i's value as the answer for top — pop top and record.
Push i.

Every index is pushed and popped at most once → amortized O(1) per step → O(n) total. The cleverness is realizing that elements we pop never come back, so the inner while loop is bounded across all iterations.

Hints

Hint 1 — what state to keep

You want to know, for each position i, where the next greater element is. What if you scanned left-to-right and kept a stack of positions whose answer is still unknown?

Hint 2 — the monotonic invariant

Maintain the invariant: values in the stack (read bottom-to-top) are strictly decreasing. When a new value arrives that's bigger than the top, the top has just found its answer — pop and record. Repeat until the stack invariant is restored, then push the new index.

Hint 3 — pseudocode

answer = [-1] * n
stack  = []         # indices whose answer is still unknown
for i in range(n):
    while stack and nums[stack[-1]] < nums[i]:
        answer[stack.pop()] = nums[i]
    stack.append(i)
return answer

Anything left on the stack at the end has no next greater — its answer stays -1.

Solution

def next_greater(nums: list[int]) -> list[int]:
    n      = len(nums)
    answer = [-1] * n
    stack  = []                       # indices whose answer is unknown
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            answer[stack.pop()] = nums[i]
        stack.append(i)
    return answer

cases = [
    ([2, 1, 2, 4, 3, 1], [4, 2, 4, -1, -1, -1]),
    ([1, 2, 3, 4],        [2, 3, 4, -1]),
    ([4, 3, 2, 1],        [-1, -1, -1, -1]),
    ([5, 5, 5],           [-1, -1, -1]),
    ([],                  []),
]
for nums, expected in cases:
    got  = next_greater(nums)
    mark = "✓" if got == expected else "✗"
    print(f"{mark} next_greater({nums}) = {got}")

function nextGreater(nums) {
  const n      = nums.length;
  const answer = new Array(n).fill(-1);
  const stack  = [];                     // indices whose answer is unknown
  for (let i = 0; i < n; i++) {
    while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
      answer[stack.pop()] = nums[i];
    }
    stack.push(i);
  }
  return answer;
}

const cases = [
  [[2, 1, 2, 4, 3, 1], [4, 2, 4, -1, -1, -1]],
  [[1, 2, 3, 4],        [2, 3, 4, -1]],
  [[4, 3, 2, 1],        [-1, -1, -1, -1]],
  [[5, 5, 5],           [-1, -1, -1]],
  [[],                  []],
];
for (const [nums, expected] of cases) {
  const got = nextGreater(nums);
  const ok  = JSON.stringify(got) === JSON.stringify(expected);
  console.log(`${ok ? "✓" : "✗"} nextGreater(${JSON.stringify(nums)}) = ${JSON.stringify(got)}`);
}

pub fn next_greater(nums: &[i32]) -> Vec<i32> {
    let n          = nums.len();
    let mut answer = vec![-1; n];
    let mut stack: Vec<usize> = Vec::new();
    for i in 0..n {
        while let Some(&top) = stack.last() {
            if nums[top] < nums[i] {
                answer[top] = nums[i];
                stack.pop();
            } else {
                break;
            }
        }
        stack.push(i);
    }
    answer
}

fn main() {
    let cases: &[(&[i32], &[i32])] = &[
        (&[2, 1, 2, 4, 3, 1], &[4, 2, 4, -1, -1, -1]),
        (&[1, 2, 3, 4],       &[2, 3, 4, -1]),
        (&[4, 3, 2, 1],       &[-1, -1, -1, -1]),
        (&[5, 5, 5],          &[-1, -1, -1]),
        (&[],                 &[]),
    ];
    for (nums, expected) in cases {
        let got  = next_greater(nums);
        let mark = if got == *expected { "✓" } else { "✗" };
        println!("{mark} next_greater({:?}) = {:?}", nums, got);
    }
}

#include <iostream>
#include <stack>
#include <vector>

std::vector<int> next_greater(const std::vector<int>& nums) {
    int n = (int)nums.size();
    std::vector<int> answer(n, -1);
    std::stack<int> st;                       // indices
    for (int i = 0; i < n; ++i) {
        while (!st.empty() && nums[st.top()] < nums[i]) {
            answer[st.top()] = nums[i];
            st.pop();
        }
        st.push(i);
    }
    return answer;
}

int main() {
    struct Case { std::vector<int> nums; std::vector<int> expected; };
    std::vector<Case> cases = {
        {{2, 1, 2, 4, 3, 1}, {4, 2, 4, -1, -1, -1}},
        {{1, 2, 3, 4},        {2, 3, 4, -1}},
        {{4, 3, 2, 1},        {-1, -1, -1, -1}},
        {{5, 5, 5},           {-1, -1, -1}},
        {{},                  {}},
    };
    for (auto& c : cases) {
        auto got = next_greater(c.nums);
        std::cout << (got == c.expected ? "✓" : "✗") << " next_greater({";
        for (size_t i = 0; i < c.nums.size(); ++i)
            std::cout << c.nums[i] << (i + 1 < c.nums.size() ? "," : "");
        std::cout << "}) = {";
        for (size_t i = 0; i < got.size(); ++i)
            std::cout << got[i] << (i + 1 < got.size() ? "," : "");
        std::cout << "}\n";
    }
}

#include <stdio.h>
#include <stdlib.h>

// Returns a malloc'd array of length n; caller frees.
int* next_greater(const int* nums, int n) {
    int* answer = malloc(n * sizeof(int));
    int* stack  = malloc(n * sizeof(int));   // indices
    int  sp     = 0;
    for (int i = 0; i < n; i++) answer[i] = -1;
    for (int i = 0; i < n; i++) {
        while (sp > 0 && nums[stack[sp - 1]] < nums[i]) {
            answer[stack[--sp]] = nums[i];
        }
        stack[sp++] = i;
    }
    free(stack);
    return answer;
}

static void show(const int* nums, int n, const int* expected) {
    int* got = next_greater(nums, n);
    int  ok  = 1;
    for (int i = 0; i < n; i++) if (got[i] != expected[i]) { ok = 0; break; }
    printf("%s next_greater({", ok ? "✓" : "✗");
    for (int i = 0; i < n; i++) printf("%d%s", nums[i], i + 1 < n ? "," : "");
    printf("}) = {");
    for (int i = 0; i < n; i++) printf("%d%s", got[i], i + 1 < n ? "," : "");
    printf("}\n");
    free(got);
}

int main(void) {
    int a [] = {2, 1, 2, 4, 3, 1}; int ea[] = {4, 2, 4, -1, -1, -1};   show(a,  6, ea);
    int b [] = {1, 2, 3, 4};       int eb[] = {2, 3, 4, -1};            show(b,  4, eb);
    int c [] = {4, 3, 2, 1};       int ec[] = {-1, -1, -1, -1};         show(c,  4, ec);
    int d [] = {5, 5, 5};          int ed[] = {-1, -1, -1};             show(d,  3, ed);
    return 0;
}

idle

The monotonic stack is the one extra idea over a plain stack that unlocks a whole family of problems. Every index enters and leaves the stack exactly once — the amortized analysis is the key insight behind the O(n) total.

Complexity

Time: O(n) amortized. Even though the inner while loop can run many times in one outer step, each index is pushed and popped at most once across the whole run.
Space: O(n) — output array plus the stack (which is at most n deep).
vs brute force: The naïve double-loop is O(n²). For n = 10⁵, that's the difference between 100 ms and 10 seconds.

In the wild

"Days until warmer weather" — given a temperature stream, how many days until a hotter one? Same algorithm, different output (days instead of value).
Stock span problem — for each day's price, how many consecutive prior days had a lower price? Symmetric (scan right-to-left).
Largest rectangle in histogram — slightly more elaborate monotonic-stack play but the same primitive.
Robot tooling — "next visible obstacle" along a depth-array slice. Monotonic stack over depth values.

Variations

Previous greater element. Scan left-to-right with a monotonic decreasing stack of values; for each i, the bottom of the maintained prefix is the previous greater. Or just scan right-to-left.
Circular next-greater. Iterate the array twice (or 2n modulo n). Anything still on the stack after the second pass really has no next greater.
Next-greater for queries (offline). With a slightly different algorithm using a monotonic stack + offline ordering, you can answer arbitrary (i, j) range questions.