Next Greater Element I — Monotonic Stack Visualization

The Problem

Given two arrays nums1 and nums2 where nums1 is a subset of nums2, find the next greater element for each element in nums1.

For each element in nums2, the next greater element is the first element to the right that is larger. If no such element exists, the answer is -1.

Example: For nums1 = [4,1,2], nums2 = [1,3,4,2]: the next greater element of 1 is 3, 4 has none (-1), and 2 has none (-1). Result: [-1, 3, -1].

Interactive Visualization

nums1 (comma-separated)

nums2 (comma-separated)

Preset

Speed:

nums2 Array

Monotonic Stack (decreasing)

Empty — elements will be pushed as the algorithm runs

Bottom ← → Top

Next Greater Map

Empty — mappings appear when elements are popped

nums1 Answers

Code

fun nextGreaterElement(nums1: IntArray, nums2: IntArray): IntArray {    val stack = ArrayDeque<Int>()    val nextGreater = mutableMapOf<Int, Int>()    for (num in nums2) {        while (stack.isNotEmpty() && stack.last() < num) {            nextGreater[stack.removeLast()] = num }        stack.addLast(num) }    return IntArray(nums1.size) { nextGreater.getOrDefault(nums1[it], -1) } }

def nextGreaterElement(nums1, nums2):    stack = []    next_greater = {}    for num in nums2:        while stack and stack[-1] < num:            next_greater[stack.pop()] = num        stack.append(num)    return [next_greater.get(n, -1) for n in nums1]

Current Step

Press Step or Play to begin.

How It Works

Key Insight

Instead of searching for the next greater element for every value using nested loops (O(n²)), we use a monotonic decreasing stack to solve the problem in a single pass through nums2. The stack holds elements that have not yet found their next greater element. When we encounter a larger value, it becomes the answer for all smaller elements sitting on the stack.

The Algorithm

Initialize an empty stack and an empty hash map next_greater.
Iterate through each element num in nums2.
While the stack is non-empty and the top of the stack is less than num: pop the top element and record next_greater[popped] = num.
Push the current element onto the stack.
After iteration, any elements remaining on the stack have no next greater element (implicitly -1).
Build the result for nums1 by looking up each value in the map: next_greater.get(n, -1).

Why a Monotonic Decreasing Stack?

The stack maintains a decreasing order from bottom to top. When a new element arrives that is larger than the stack top, we know this element is the first greater element to the right for whatever is on top. We keep popping until the stack property is restored. This guarantees each element is pushed and popped at most once, giving us amortized O(1) per element.

Complexity

Time O(n)

Space O(n)

Each element in nums2 is pushed onto the stack exactly once and popped at most once, so the total number of stack operations is O(n). The hash map stores at most n entries. Building the result for nums1 takes O(m) where m is the length of nums1.