Next Greater Element I | Monotonic Stack

leetcode.com

Problem Statement

You are given two arrays:

• nums1 is a subset of nums2.
• For every element in nums1, find the first greater element to its right in nums2.

If no greater element exists, return -1.

Brute Force Intuition

In an interview, you can explain it like this:

For every element in nums1, first locate its position in nums2. Then traverse towards the right until a greater element is found.

Although simple, this repeatedly scans the same elements.

Complexity

• Time Complexity: O(N × M)
• Space Complexity: O(1)

Brute Force Code

class Solution {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        int[] ans = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {

            int index = -1;

            // Find element in nums2
            for (int j = 0; j < nums2.length; j++) {

                if (nums2[j] == nums1[i]) {
                    index = j;
                    break;
                }
            }

            ans[i] = -1;

            // Search towards right
            for (int j = index + 1; j < nums2.length; j++) {

                if (nums2[j] > nums1[i]) {
                    ans[i] = nums2[j];
                    break;
                }
            }
        }

        return ans;
    }
}

Moving Towards the Optimal Approach

Notice that while scanning every element, we repeatedly search the right side.

Instead, can we compute the next greater element for every element in nums2 only once?

Yes!

We'll use a Monotonic Decreasing Stack.

Pattern Recognition

Whenever you see:

• Next Greater Element
• Previous Greater Element
• Next Smaller Element
• Previous Smaller Element

Think:

Monotonic Stack

Key Observation

Traverse nums2 from right to left.

Maintain a stack such that:

Top of stack
=
First Greater Element

Before pushing the current element:

Remove all smaller elements because they'll never become the next greater for future elements.

Optimal Approach

For every element:

Remove all smaller elements.

If stack becomes empty:

Next Greater = -1

Else:

Next Greater = Stack Top

Store this mapping in a HashMap.

Finally, answer each query in nums1 using the map.

Optimal Java Solution

class Solution {

    public int[] nextGreaterElement(int[] nums1, int[] nums2) {

        HashMap<Integer, Integer> map = new HashMap<>();

        Stack<Integer> st = new Stack<>();

        for (int i = nums2.length - 1; i >= 0; i--) {

            while (!st.isEmpty() && st.peek() < nums2[i]) {
                st.pop();
            }

            if (st.isEmpty()) {
                map.put(nums2[i], -1);
            } else {
                map.put(nums2[i], st.peek());
            }

            st.push(nums2[i]);
        }

        int[] ans = new int[nums1.length];

        for (int i = 0; i < nums1.length; i++) {
            ans[i] = map.get(nums1[i]);
        }

        return ans;
    }
}

Dry Run

Input

nums1 = [2,4]

nums2 = [1,2,3,4]

Traverse from right:

Step 1

Current = 4

Stack = []

Next Greater = -1

Push 4

Stack:

4

Step 2

Current = 3

Stack Top = 4

Next Greater = 4

Push 3

Stack:

3
4

Step 3

Current = 2

Stack Top = 3

Next Greater = 3

Push 2

Stack:

2
3
4

Step 4

Current = 1

Stack Top = 2

Next Greater = 2

HashMap becomes:

1 → 2

2 → 3

3 → 4

4 → -1

Answer:

2 → 3

4 → -1

Result:

[3, -1]

Why Monotonic Stack Works?

Every element enters the stack once.

Every element leaves the stack once.

The stack always maintains elements in decreasing order.

Hence:

Top of stack
=
Nearest Greater Element

without repeatedly scanning the array.

Complexity Analysis

Metric	Complexity
Time Complexity	O(N + M)
Space Complexity	O(N)

Where:

• N = nums2.length
• M = nums1.length

Interview One-Liner

Traverse from right to left using a monotonic decreasing stack to precompute the next greater element for every value, then answer queries in O(1) using a HashMap.

Pattern Learned

Next Greater Element
+
Nearest Greater
+
Right Side Query

=> Monotonic Decreasing Stack

Similar Problems

• Next Greater Element I
• Next Greater Element II
• Daily Temperatures
• Stock Span Problem
• Next Smaller Element
• Previous Greater Element

Memory Trick

Think:

Current Element
       ↓
Remove Smaller Elements
       ↓
Stack Empty ?
       ↓
Yes → -1

No → Stack Top

Mental Model

Need Nearest Greater on Right

↓

Traverse Right to Left

↓

Maintain Decreasing Stack

↓

Top = Answer

Whenever you hear:

"Find the next greater element"

your brain should immediately think:

Monotonic Stack