Next Greater Element I — DSA Visualizer

Problem

The next greater element of some element x in array nums2 is the first element to the right of x in nums2 that is strictly greater. Given nums1 (a subset of nums2), for each element in nums1, find its next greater element in nums2. Return -1 if it does not exist.

Example 1

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

Output: [-1,3,-1]

Explanation: 4 has no greater→-1; 1→next greater is 3; 2→no greater→-1.

Example 2

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

Output: [3,-1]

Explanation: 2→next greater is 3; 4→no greater→-1.

Constraints: 1 ≤ nums1.length ≤ nums2.length ≤ 1000 | All integers in nums1 and nums2 are unique.

nums2 — Source Array

Monotonic Stack (decreasing, bottom→top)

stack (top↑)

Next-Greater Map element → nextGreater

{ }

nums1 — Query Results

Variables

i (nums2)

—

nums2[i]

—

stack top

—

map size

Step Logic

Select an example above and press Play.

Ready

0 / 0

Select an example above and press Play.

Algorithm

Init empty map and stack

For each n in nums2: while stack top < n, pop and record map[top] = n

Push n onto the stack (stack stays decreasing)

Remaining stack elements have no next greater → implicitly -1

For each element in nums1: look up in map, default -1

Time

O(n+m)

Space

O(n)

Why Monotonic Stack Works

We keep the stack in decreasing order. When a new element n is encountered and it is larger than the top, that top element has finally found its next greater element. We pop and record it. Elements that never get popped have no next greater element (they remain -1). The HashMap then gives O(1) lookup for any query in nums1.