Embedded Prep

If you’re preparing for coding interviews or practicing data structure problems, chances are you’ll encounter the Next Greater Element in array problem. It’s one of the most common and important questions related to arrays and stacks — frequently asked by top tech companies.

In this beginner-friendly tutorial, we’ll explore the concept of Next Greater Element in an array with simple logic, step-by-step explanation, dry run examples, and multiple code implementations (brute-force and stack-based).

Whether you’re a student, a beginner programmer, or an aspiring software developer, this guide will help you build a strong foundation in solving array problems using stacks..

What is the Next Greater Element?

The Next Greater Element in array is a classic coding interview problem that tests your understanding of arrays and stack-based logic.

Here’s the problem statement:

Given an array of integers, your task is to find the next greater element for each element in the array.
The next greater element for an element x is the first element to the right of x that is greater than x.

If no greater element exists on the right side, the answer is -1 for that position.

🔍 Example:

Input:  [4, 5, 2, 25]
Output: [5, 25, 25, -1]

Explanation:

• Next greater of 4 is 5
• Next greater of 5 is 25
• Next greater of 2 is 25
• 25 has no greater element, so answer is -1

This concept is commonly used in problems involving stock span, daily temperatures, and monotonic stacks. Understanding the Next Greater Element in array is a stepping stone to solving more advanced array-based questions.

Brute Force Approach to Find Next Greater Element in Array (Easy to Understand)

✅ Logic:

In this basic approach to solving the Next Greater Element in array, we use two nested loops. For each element in the array, we scan all elements to its right and find the first greater element.

If we don’t find any, we simply put -1.

🔁 Time Complexity:

• O(n²) – Because for each element, we loop through the remaining elements on its right.

This method is easy to understand but not efficient for large input sizes.

🧑‍💻 C++ Code: Brute Force for Next Greater Element

#include <iostream>
#include <vector>
using namespace std;

void printNGE(vector<int>& arr) {
    int n = arr.size();
    for(int i = 0; i < n; i++) {
        int next = -1;
        for(int j = i + 1; j < n; j++) {
            if(arr[j] > arr[i]) {
                next = arr[j];
                break;
            }
        }
        cout << arr[i] << " --> " << next << endl;
    }
}

int main() {
    vector<int> arr = {4, 5, 2, 25};
    printNGE(arr);
    return 0;
}

Efficient Stack-Based Approach to Next Greater Element in Array (O(n) Time)

When solving the Next Greater Element in array, an efficient solution is to use a stack. This reduces the time complexity from O(n²) to O(n) and is widely asked in coding interviews.

🧠 Logic:

We process the array from right to left, using a stack to keep track of potential next greater candidates.

📚 Step-by-Step Dry Run:

For input array: [4, 5, 2, 25]

1. Start from the rightmost element.
2. For each element:
   • Remove all elements from the stack smaller than or equal to it.
   • If the stack becomes empty, the next greater element is -1.
   • Otherwise, the top of the stack is the next greater.
3. Push the current element onto the stack for future comparisons.

🧑‍💻 C++ Code: Stack-Based Next Greater Element

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<int> nextGreaterElement(vector<int>& arr) {
    int n = arr.size();
    vector<int> result(n, -1);
    stack<int> st;

    for(int i = n - 1; i >= 0; i--) {
        // Pop elements smaller than or equal to arr[i]
        while(!st.empty() && st.top() <= arr[i]) {
            st.pop();
        }

        // If stack is not empty, top is the next greater element
        if(!st.empty()) {
            result[i] = st.top();
        }

        // Push current element
        st.push(arr[i]);
    }

    return result;
}

int main() {
    vector<int> arr = {4, 5, 2, 25};
    vector<int> res = nextGreaterElement(arr);

    for(int i = 0; i < arr.size(); i++) {
        cout << arr[i] << " --> " << res[i] << endl;
    }

    return 0;
}

🎯 Output:

4 --> 5  
5 --> 25  
2 --> 25  
25 --> -1

✅ Why Stack is Useful for Next Greater Element Problems?

Using a stack makes this problem highly efficient because it stores elements in a last-in, first-out (LIFO) structure, allowing us to track potential next greater elements without scanning the whole array repeatedly.

This stack-based method is especially powerful for large datasets and is frequently used in:

• Stock span problems
• Temperature prediction arrays
• Monotonic stack patterns

Time & Space Complexity Summary

Approach	Time Complexity	Space Complexity
Brute Force	O(n²)	O(1)
Stack-based Method	O(n)	O(n)

More Problems Related to Next Greater Element in Array

Once you’re comfortable with the concept, try solving these related variations:

• ✅ Next Smaller Element in Array
• ✅ Next Greater Element in Circular Array
• ✅ Previous Greater Element in Array
• ✅ Daily Temperatures Problem (LeetCode)
• ✅ Stock Span Problem

Final Words

The Next Greater Element in array is a foundational algorithm that helps build problem-solving skills involving arrays, stacks, and greedy logic.

If you understand both the brute force and optimized approaches, you’ll be able to solve a wide range of real-world problems that follow a similar pattern.

Keep practicing and exploring new variations — and remember: every great coder once started with basics like this!

You can also Visit other tutorials of Embedded Prep 

• Structure with Pointers
• Master How to Use a Saleae Logic Analyzer with Arduino Uno (2025)
• Top 30+ I2C Interview Questions
• Bit Manipulation Interview Questions
• Structure and Union in c
• Fault Handling in Arm Cortex Mx Processor
• Merge sort algorithm

Special thanks to @mr-raj for contributing to this article on EmbeddedPrep