Stage 4: Advanced Techniques·Monotonic Stack & Deque

Easy#4967 min readMonotonic StackHashingLeetCode

Next Greater Element I

Monotonic stack

The basic pattern. Process right to left, stack holds candidates.

Published Apr 15, 2026

Problem

You're given two arrays: nums1 is a subset of nums2, both contain distinct integers.

For each element x in nums1, find the next greater element in nums2 — the first number to the right of x in nums2 that is strictly larger than x. If there is no such number, return -1.

Input

nums1 = [4, 1, 2], nums2 = [1, 3, 4, 2]

Output

[-1, 3, -1]

Explanation

4 has no greater to its right; 1's next greater is 3; 2 has no greater to its right.

Input

nums1 = [2, 4], nums2 = [1, 2, 3, 4]

Output

[3, -1]

Intuition

Brute force: for each element of nums1, find it in nums2 and scan right. O(n × m).

The key reframe: precompute the "next greater" map for every element of nums2 in a single pass. Then nums1 becomes a sequence of O(1) lookups. Building that map in one pass is exactly what a monotonic stack does — each element enters and leaves the stack at most once.

Approach

Brute Force

TimeO(n · m)

SpaceO(1)

For each value in nums1, find it in nums2 and scan forward until something bigger appears (or we run out). Two nested loops. Fine for tiny inputs; doesn't scale and doesn't teach the pattern.

impl Solution {
    pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        nums1
            .iter()
            .map(|&y| {
                let i = nums2.iter().position(|&x| x == y).unwrap();
                nums2[i + 1..]
                    .iter()
                    .find(|&&x| x > y)
                    .copied()
                    .unwrap_or(-1)
            })
            .collect()
    }
}

Rust · runnable

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  return nums1.map((y) => {
    const i = nums2.indexOf(y);
    for (let j = i + 1; j < nums2.length; j++) {
      if (nums2[j] > y) return nums2[j];
    }
    return -1;
  });
}

TypeScript · runnable

Monotonic Stack

TimeO(n + m)

SpaceO(n)

Recommended

Walk nums2 once. Maintain a decreasing stack of values whose next-greater we haven't found yet. When we see a new x, pop every stack element smaller than x — their next greater is x. Push x.

Each value enters and leaves the stack at most once, so the total work is linear — the while loop looks quadratic but amortizes to O(n).

use std::collections::HashMap;

impl Solution {
    pub fn next_greater_element(nums1: Vec<i32>, nums2: Vec<i32>) -> Vec<i32> {
        let mut next_greater: HashMap<i32, i32> = HashMap::with_capacity(nums2.len());
        let mut stack: Vec<i32> = Vec::with_capacity(nums2.len());

        for &x in &nums2 {
            while let Some(&top) = stack.last() {
                if top < x {
                    stack.pop();
                    next_greater.insert(top, x);
                } else {
                    break;
                }
            }
            stack.push(x);
        }

        nums1
            .into_iter()
            .map(|y| *next_greater.get(&y).unwrap_or(&-1))
            .collect()
    }
}

Rust · runnable

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
  const nextGreater = new Map<number, number>();
  const stack: number[] = [];

  for (const x of nums2) {
    while (stack.length > 0 && stack[stack.length - 1] < x) {
      nextGreater.set(stack.pop()!, x);
    }
    stack.push(x);
  }

  return nums1.map((y)=> nextGreater.get(y) ?? -1);
}

TypeScript · runnable

Trace

Monotonic stack pass over nums2 = [1, 3, 4, 2]:

x	stack before	pops	stack after	map updates
1	[]	—	[1]	—
3	[1]	pop 1 (1 < 3)	[3]	map[1] = 3
4	[3]	pop 3 (3 < 4)	[4]	map[3] = 4
2	[4]	—	[4, 2]	—

Final map = {1: 3, 3: 4}. Leftovers [4, 2] have no next greater → default -1.

For nums1 = [4, 1, 2]: [-1, 3, -1]. ✓

Edge cases

Descending nums2 — nothing pops; map stays empty; all nums1 answers are -1.
Ascending nums2 — every element pops the previous; n - 1 map entries.
nums1 element not in nums2 — ruled out by the problem; ?? -1 handles accidental drift.

💡

Tip

The circular variant (#503) iterates nums2 twice — suppress pushes on the second pass but still pop. Same core algorithm.

Takeaway

Whenever a problem asks "for each element, find the nearest one to the left/right with some property," reach for a monotonic stack. Increasing stack for "next smaller", decreasing stack for "next greater".

This pattern solves a whole class of hards — #739 Daily Temperatures, #84 Largest Rectangle, #85 Maximal Rectangle — and is directly relevant to order-book processing and time-series analytics in production systems.

Medium#503

Next Greater Element II

Circular array — iterate twice through the array.

Medium#739

Daily Temperatures

Your first monotonic stack! ‘Next greater element’ pattern.

Hard#84

Largest Rectangle in Histogram

THE canonical mono stack problem. Must solve in under 15 minutes.