Next Greater Element Explained: Brute Force vs Monotonic Stack (C++) | LeetCode 496

Welcome back to the world of Stacks! If you have already conquered the Valid Parentheses problem, you are ready for the next major milestone in technical interviews: the Monotonic Stack.

The Next Greater Element problem is the ultimate gateway to understanding this powerful pattern. Whether you are prepping for a FAANG interview or just trying to survive your college placement coding rounds, mastering this concept is non-negotiable.

In this guide, we will break down the problem from first principles, explore the intuitive (but slow) brute-force method, and then unveil the magic of the Monotonic Stack in C++.

Let's get started!

Introduction

What is a "Next Greater Element"?

Imagine you are standing in a line of people, looking to your right. The "Next Greater Element" is simply the first person you see who is taller than you. If everyone to your right is shorter than you, your Next Greater Element doesn't exist (usually represented as -1).

Why is this a Common Interview Question?

This problem introduces the Monotonic Stack—a stack whose elements are always sorted (either entirely increasing or entirely decreasing). Interviewers use this problem to see if you can optimize a nested-loop brute force O(N^2) solution down to a blazing-fast O(N) solution by cleverly managing memory.

Real-World Applications

• Stock Market Analysis: Finding the next day the stock price will be higher than today's price.
• Weather Forecasting: Calculating how many days you have to wait for a warmer temperature (very similar to LeetCode 739: Daily Temperatures).
• UI/UX Rendering: Calculating lines of sight in 2D gaming environments.

Problem Statement

The Problem (LeetCode 496 - Next Greater Element I): You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.

For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.

Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.

Examples

Example 1:

• Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
• Output: [-1,3,-1]
• Explanation:
  • For 4 in nums1, we find it in nums2. There is no number to the right of 4 that is greater than it. Output: -1.
  • For 1 in nums1, the next greater number to its right in nums2 is 3. Output: 3.
  • For 2 in nums1, there is no number to its right. Output: -1.

Example 2:

• Input: nums1 = [2,4], nums2 = [1,2,3,4]
• Output: [3,-1]
• Explanation:
  • For 2, the next greater number to its right is 3.
  • For 4, there is no number to its right.

Example 3:

• Input: nums1 = [3,1], nums2 = [3,1,2]
• Output: [-1,2]
• Explanation:
  • For 3, it is the largest and first element. Nothing greater to the right. Output -1.
  • For 1, the next greater element to the right is 2. Output: 2.

Constraints

• 1 <= nums1.length <= nums2.length <= 1000
• 0 <= nums1[i], nums2[i] <= 10^4
• All integers in nums1 and nums2 are unique.
• All the integers of nums1 also appear in nums2.

Why these constraints matter:

1. Uniqueness: Because all numbers are unique, we can safely use a Hash Map to store a number as a key and its Next Greater Element as the value. We don't have to worry about duplicate keys.
2. Subset relation: We can process the entirety of nums2 first to find everyone's Next Greater Element, and then just look up the answers for the specific numbers requested in nums1.

Observations

When we look for the next greater element, notice what happens when we encounter a very large number:

Imagine the array: [5, 4, 3, 2, 1, 10] The numbers 5, 4, 3, 2, 1 are all waiting for a greater element. The moment we see 10, it becomes the next greater element for all of them!

Key Insight: We need a way to keep track of elements that are "waiting" to find their next greater element. When we find a large number, we should resolve the wait for the smallest waiting numbers first (the most recently seen ones). This "Last-In, First-Out" waiting list perfectly describes a Stack.

Approach 1: Brute Force (Educational)

Let's start with the most obvious way to solve this, which mimics how a human would do it manually.

Intuition

For every number in nums1, find where it lives in nums2. Once you find it, scan to the right in nums2 until you find a strictly greater number. If you reach the end of nums2 without finding one, the answer is -1.

Algorithm

1. Create a result array ans.
2. Loop through each element x in nums1.
3. Loop through nums2 to find the element x.
4. Once found, continue looping right in nums2.
5. The first number you see that is > x is the answer. Break the loop and store it.
6. If the loop finishes without finding a larger number, store -1.

Dry Run

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

• Process 4: Find 4 in nums2 at index 2. Look right: [2]. No element > 4. Result for 4 is -1.
• Process 1: Find 1 in nums2 at index 0. Look right: [3, 4, 2]. 3 > 1. Result for 1 is 3.
• Process 2: Find 2 in nums2 at index 3. Look right: []. Nothing there. Result for 2 is -1.

C++ Implementation

#include <vector>

using namespace std;

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ans;  // Result vector to store answers for each element in nums1
        
        // Loop through each element in nums1
        for (int i = 0; i < nums1.size(); i++) {
            int current = nums1[i];   // The element we are finding the next greater for
            int nextGreater = -1;     // Default value if no greater element is found
            bool found = false;       // Flag to check if current element is located in nums2
            
            // Traverse nums2 to find the next greater element
            for (int j = 0; j < nums2.size(); j++) {
                // Step 1: Locate the element in nums2
                if (nums2[j] == current) {
                    found = true;  // Mark that we found the element
                }
                // Step 2: Once found, look for the first element strictly greater
                if (found && nums2[j] > current) {
                    nextGreater = nums2[j];  // Assign the next greater element
                    break;                   // Stop searching further
                }
            }
            
            // Push the result (either the next greater element or -1 if not found)
            ans.push_back(nextGreater);
        }
        
        return ans;  // Return the final result vector
    }
};

Complexity Analysis

Verdict: While this works perfectly fine for lengths up to 1,000 (taking ~1,000,000 operations, well under the 1-second time limit), it scales terribly. If nums2 had 100,000 elements, this code would time out and fail the interview.

Approach 2: Optimal Monotonic Stack Solution

To achieve an O(N) solution, we cannot afford to scan nums2 multiple times. We must process nums2 in a single pass.

Intuition

We will iterate through nums2 from left to right. We will use a stack to keep track of numbers that haven't found their next greater element yet.

• If the current number is smaller than the top of the stack, it just joins the stack (starts waiting).
• If the current number is greater than the top of the stack, eureka! We just found the next greater element for the top of the stack. We pop it, record the answer in a Hash Map, and keep checking the new top of the stack.

Because we only keep smaller and smaller elements waiting on top of each other, the stack is always sorted in decreasing order from bottom to top. This is called a Monotonic Decreasing Stack.

Algorithm

1. Initialize an empty stack st and an unordered map ngeMap.
2. Iterate through each number num in nums2:
   • While the stack is NOT empty AND num is strictly greater than the top of the stack:
     • We found an answer! ngeMap[st.top()] = num.
     • Pop the top element off the stack.
   • Push the current num onto the stack (it is now waiting for its own greater element).
3. After the loop, any numbers still left in the stack never found a greater element. Map them to -1.
4. Iterate through nums1 and build the result array by looking up each element in ngeMap.

Dry Run

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

Now, mapping nums1 = [4, 1, 2]:

• Map lookup for 4 -> -1
• Map lookup for 1 -> 3
• Map lookup for 2 -> -1
• Output: [-1, 3, -1]. Perfect!

Visual Illustration

Let's visualize the stack process for nums2 = [2, 1, 3]:

C++ Implementation

Here is the highly optimized, LeetCode-compatible code.

#include <vector>
#include <unordered_map>
#include <stack>

using namespace std;

class Solution {
public:
    vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
        unordered_map<int, int> ngeMap; // Map to store Next Greater Element (NGE) for each number in nums2
        stack<int> st;                  // Monotonic stack to keep track of decreasing sequence
        
        // Step 1: Process nums2 to compute NGE for every element
        for (int num : nums2) {
            // While stack is not empty AND current number is greater than stack's top
            // → This means current number is the NGE for the stack's top element
            while (!st.empty() && num > st.top()) {
                ngeMap[st.top()] = num; // Record the NGE for stack's top
                st.pop();               // Pop since its NGE is found
            }
            // Push current number onto stack (waiting for its NGE)
            st.push(num);
        }
        
        // Step 2: Remaining elements in stack have no greater element to their right
        while (!st.empty()) {
            ngeMap[st.top()] = -1; // Assign -1 as no NGE exists
            st.pop();
        }
        
        // Step 3: Build the final answer for nums1 using precomputed map
        vector<int> ans;
        for (int num : nums1) {
            ans.push_back(ngeMap[num]); // Lookup NGE directly from map
        }
        
        return ans; // Return the result vector
    }
};

Complexity Analysis

Why Stack Works (The Monotonic Concept)

To make this completely intuitive, imagine you are a teacher looking over a classroom of students standing in a line.

If a 5-foot tall student is standing in front of a 6-foot tall student, you can easily see the 6-foot student. But if the 6-foot student is standing in front of the 5-foot student, the shorter student is blocked from view.

The Monotonic Stack works exactly like this. By popping smaller elements when a larger element arrives, the stack effectively "removes" numbers that have been blocked or whose search is officially over. It only keeps a strictly decreasing "line of sight" memory.

Comparison Table

Edge Cases

Always discuss edge cases with your interviewer:

• Strictly Decreasing Array ([5, 4, 3, 2, 1]): The while loop condition (num > st.top()) is never met. Everything stays in the stack and ultimately gets mapped to -1. Handled flawlessly.
• Strictly Increasing Array ([1, 2, 3, 4, 5]): Every element immediately pops the previous element. Stack size never exceeds 1 during the for loop. Handled flawlessly.
• Single Element (nums2 = [1]): Loop runs once, pushes 1, finishes, maps 1 to -1. Handled perfectly.

Common Mistakes

1. Stacking Indices vs Values: For this specific problem (LC 496), the arrays contain unique values, so we can push the actual values onto the stack. For other Monotonic Stack problems (like LC 739), there are duplicate values. Best practice: Get into the habit of pushing array indices onto the stack, not the values themselves.
2. Wrong Inequality Sign: Using num < st.top() instead of num > st.top() will result in building an increasing stack instead of resolving a decreasing stack.
3. Forgetting to Empty the Stack: If you don't map the remaining elements in the stack to -1 at the end, your hash map lookups might return default values (which is 0 in C++, not -1).

Interview Tips

• Drop the Name: Explicitly say to the interviewer, "I am going to use a Monotonic Decreasing Stack for this." It demonstrates deep understanding of algorithmic patterns.
• Explain the Map: Clarify why the hash map is needed. Say, "Because nums1 is a subset in a different order, I need O(1) lookups to fetch the answers we computed from nums2."
• Forward vs Backward: Note that there are two ways to write this algorithm. You can iterate from left-to-right (like we did), or right-to-left. Both are valid! Left-to-right is often more intuitive for beginners ("Who is waiting for a taller person?").

FAQs

1. What exactly is a Monotonic Stack? It is simply a normal Stack data structure where we strictly enforce an order (either entirely ascending or descending) before pushing a new element. We do this by popping elements that violate the rule.

2. Why do we need an unordered_map? We find the answers for nums2, but the problem asks for the answers corresponding to the elements in nums1. The map allows us to connect the element to its answer in O(1) time.

3. Can this be solved without extra space? No. Because you have to remember elements that haven't found a greater element yet, and you have to map them to nums1, O(N) auxiliary space is mathematically unavoidable.

4. Why is the time complexity O(N) if there is a while loop inside a for loop? This is a classic interview question! While it looks like O(N^2), remember that every element is pushed onto the stack exactly once, and popped exactly once. Over the entire for loop, the while loop body executes at most N times total, not N times per iteration.

5. What if there were duplicate numbers in the arrays? If there were duplicates, storing values in the map wouldn't work (keys must be unique). We would have to push the indices of the elements onto the stack instead of the values.

6. Can we iterate backwards to solve this? Yes! If you loop nums2 from right-to-left, the stack maintains a list of "potential next greater elements". It works equally well and is the preferred template for some advanced programmers.

7. Is this asked in real interviews? Yes. Amazon, Meta, and Bloomberg frequently ask Monotonic Stack variations.

8. Why map remaining elements to -1 explicitly? In C++, if you query a missing key in an unordered_map, it automatically inserts the key with a default value of 0. Since 0 could be a valid next greater element, returning 0 instead of -1 would cause test failures.

9. Are stacks actually used in real-world systems like this? Yes, compilers use this exact logic to parse syntax, and financial algorithms use it to detect price peaks and valleys in time-series data.

10. What is the difference between a Monotonic Decreasing and Increasing Stack? Decreasing stacks are used to find the "Next Greater Element". Increasing stacks are used to find the "Next Smaller Element".

video link:

code link:

https://leetcode.com/problems/next-greater-element-i/