Next Greater Element in Python | Monotonic Stack Explained (LeetCode 496)

Next Greater Element – Monotonic Stack Approach (LeetCode 496)

The Next Greater Element problem is a classic application of the monotonic stack pattern. The goal is to find, for each element in nums1, the first greater element to its right in nums2. If no such element exists, we return -1.

---

Key Observations

• The relative order of elements in nums2 matters.
• Brute force would lead to an O(n²) solution.
• A monotonic decreasing stack allows us to solve this in linear time.

---

Core Idea (Monotonic Stack)

We traverse nums2 from right to left and maintain a stack such that:

• The stack always contains elements in decreasing order.
• Elements smaller than or equal to the current value are popped.
• The top of the stack (if it exists) is the next greater element.

We store the result in a hashmap so that we can answer queries for nums1 in constant time.

---

Python Implementation

class Solution:
    def nextGreaterElement(self, nums1, nums2):
        nge = {}
        stack = []

        for i in range(len(nums2) - 1, -1, -1):
            while stack and stack[-1] <= nums2[i]:
                stack.pop()

            nge[nums2[i]] = stack[-1] if stack else -1
            stack.append(nums2[i])

        return [nge[x] for x in nums1]

---

Time & Space Complexity

• Time Complexity: O(n + m)
• Space Complexity: O(n)

Each element is pushed and popped from the stack at most once, ensuring optimal performance.

---

Why This Approach Works Well in Interviews

• Demonstrates understanding of stack-based optimization
• Clearly avoids brute force
• Easily extendable to similar problems like circular arrays

---

GitHub Reference

You can find the complete solution here:

👉 View on GitHub (LC496.py)

---

Tip: This monotonic stack pattern appears frequently in problems involving "next", "previous", or "nearest" greater/smaller elements. Mastering this template can unlock multiple problems at once.