Next Greater Element I: LeetCode 496 Monotonic Stack Solution

Next Greater Element I (#496) is one of those LeetCode problems that looks deceptively simple on the surface but teaches a pattern you will use over and over again in coding interviews. The core idea is elegant — precompute the next greater element for every value in an array using a monotonic stack, store the results in a hash map, and then answer any query in constant time.

If you have ever struggled with problems that ask "what is the next larger value to the right?" this is the problem to start with. The next greater element leetcode pattern shows up in Daily Temperatures (#739), Stock Span (#901), Largest Rectangle in Histogram (#84), and many more. Once you internalize the approach here, those harder problems become variations rather than entirely new challenges.

In this walkthrough, you will learn exactly how the monotonic stack works, why a hash map makes the two-array lookup efficient, and how to implement the full solution in O(n + m) time. No brute force needed.

You are given two arrays: nums1 and nums2. Every element in nums1 is also present in nums2, and all elements in nums2 are unique. For each element in nums1, you need to find its next greater element in nums2 — that is, the first element to its right in nums2 that is strictly larger. If no such element exists, return -1.

For example, given nums1 = [4, 1, 2] and nums2 = [1, 3, 4, 2], the answer is [-1, 3, -1]. The element 4 has no greater element to its right in nums2. The element 1 has 3 as its next greater element. The element 2 also has no greater element to its right.

The naive approach would check every element in nums1, find it in nums2, and scan rightward for the next greater value. That runs in O(n * m) time. But nums2 contains all the information you need — if you precompute the next greater element for every value in nums2 first, each nums1 lookup becomes O(1).

The key insight is that you can process nums2 once with a monotonic decreasing stack to find the next greater element for every value. As you iterate through nums2 left to right, you maintain a stack where each element is greater than or equal to the one above it. When you encounter a value larger than the stack top, you pop and record that the popped element's next greater is the current value.

Every time you pop an element from the stack, you store the mapping in a hash map: popped element maps to current element. After processing all of nums2, any elements remaining on the stack have no next greater element — they map to -1. This entire pass takes O(n) time where n is the length of nums2.

Once the hash map is built, answering queries from nums1 is trivial. For each element in nums1, look it up in the map. If it exists, return the mapped value. If not, return -1. The total time complexity is O(n + m) where n is the length of nums2 and m is the length of nums1.

The implementation follows a clean two-phase structure. First, build the next-greater map from nums2 using the monotonic stack. Second, construct the result array by looking up each nums1 element in the map.

Initialize an empty stack and an empty hash map. Iterate through each element in nums2. While the stack is not empty and the current element is greater than the stack top, pop the top and set map[popped] = current. Then push the current element onto the stack. After the loop, all remaining stack elements have no next greater element.

For the result, iterate through nums1 and for each value, return map.get(value) if it exists, otherwise -1. The code is concise — typically 10-12 lines in Python or JavaScript. The stack never holds more than n elements total across all push and pop operations, confirming the O(n) time complexity.

Let us trace through the algorithm step by step with the example. We process nums2 = [1, 3, 4, 2] and build the next-greater map.

Step 1: Process 1. Stack is empty, push 1. Stack: [1]. Step 2: Process 3. Stack top is 1, and 3 > 1, so pop 1 and set map[1] = 3. Stack is empty. Push 3. Stack: [3]. Map: {1: 3}.

Step 3: Process 4. Stack top is 3, and 4 > 3, so pop 3 and set map[3] = 4. Stack is empty. Push 4. Stack: [4]. Map: {1: 3, 3: 4}. Step 4: Process 2. Stack top is 4, and 2 < 4, so do nothing. Push 2. Stack: [4, 2]. Map unchanged.

After processing all of nums2, stack contains [4, 2]. These elements have no next greater value, so map[4] = -1 and map[2] = -1. Final map: {1: 3, 3: 4, 4: -1, 2: -1}.

Now look up each element of nums1 = [4, 1, 2]: map[4] = -1, map[1] = 3, map[2] = -1. Result: [-1, 3, -1]. Done in one pass through nums2 and one pass through nums1.

When nums1 equals nums2, every element needs a next-greater lookup and the problem reduces to finding next greater element for the entire array. The algorithm handles this naturally since every element is in the map after processing nums2.

When nums2 is strictly decreasing (e.g., [5, 4, 3, 2, 1]), nothing ever gets popped from the stack during processing. Every element stays on the stack until the end, and the entire result is filled with -1. The algorithm still runs in O(n) — it just never triggers the inner while loop.

When nums2 is strictly increasing (e.g., [1, 2, 3, 4, 5]), every element gets popped immediately when the next element is processed. Each element's next greater is simply the element directly after it. The stack never grows beyond size 1.

Next Greater Element I is the foundation problem for the monotonic stack pattern. The technique of maintaining a stack of candidates and popping when a larger value arrives is the exact same approach used in Daily Temperatures (#739), where you track how many days until a warmer temperature. It is also the core of Stock Span (#901), where you look backward for the previous greater element instead of forward.

The deeper lesson is about precomputation. Instead of answering each query independently in O(n) time, you invest O(n) upfront to build a lookup structure that makes every query O(1). This trade-off — preprocessing time for query speed — appears throughout algorithm design, from prefix sums to sparse tables to segment trees.

If you can solve Next Greater Element I confidently, challenge yourself with Next Greater Element II (#503) which uses a circular array, and Largest Rectangle in Histogram (#84) which extends the monotonic stack to track indices. Practice the pattern with YeetCode flashcards until the monotonic stack setup becomes automatic — recognizing when to reach for this tool is half the battle in interviews.