DEV Community

Jaspreet singh
Jaspreet singh

Posted on

Next Greater Element I | Monotonic Stack

#algorithms #interview #java #leetcode
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;
    }
}
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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.
Enter fullscreen mode Exit fullscreen mode

If stack becomes empty:

Next Greater = -1
Enter fullscreen mode Exit fullscreen mode

Else:

Next Greater = Stack Top
Enter fullscreen mode Exit fullscreen mode

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;
    }
}
Enter fullscreen mode Exit fullscreen mode

Dry Run

Input 

nums1 = [2,4]

nums2 = [1,2,3,4]
Enter fullscreen mode Exit fullscreen mode

Traverse from right:

Step 1 

Current = 4

Stack = []

Next Greater = -1

Push 4
Enter fullscreen mode Exit fullscreen mode

Stack:

4
Enter fullscreen mode Exit fullscreen mode

Step 2 

Current = 3

Stack Top = 4

Next Greater = 4

Push 3
Enter fullscreen mode Exit fullscreen mode

Stack:

3
4
Enter fullscreen mode Exit fullscreen mode

Step 3 

Current = 2

Stack Top = 3

Next Greater = 3

Push 2
Enter fullscreen mode Exit fullscreen mode

Stack:

2
3
4
Enter fullscreen mode Exit fullscreen mode

Step 4 

Current = 1

Stack Top = 2

Next Greater = 2
Enter fullscreen mode Exit fullscreen mode

HashMap becomes:

1 → 2

2 → 3

3 → 4

4 → -1
Enter fullscreen mode Exit fullscreen mode

Answer:

2 → 3

4 → -1
Enter fullscreen mode Exit fullscreen mode

Result:

[3, -1]
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Mental Model 

Need Nearest Greater on Right

↓

Traverse Right to Left

↓

Maintain Decreasing Stack

↓

Top = Answer
Enter fullscreen mode Exit fullscreen mode

Whenever you hear:

"Find the next greater element"

your brain should immediately think:

Monotonic Stack

Top comments (0)