Next Greater Element in C, C++, Java & Python – Code with Explanation & Examples in Short and Simple

   

C Program

#include <stdio.h>
int main(){
    int a[]={4,5,2,25},n=4,st[100],t=-1,res[4];
    for(int i=n-1;i>=0;i--){
        while(t!=-1 && st[t]<=a[i]) t--;
        res[i]=(t==-1)?-1:st[t];
        st[++t]=a[i];
    }
    for(int i=0;i<n;i++) printf("%d ",res[i]);
}

C Output

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

C++ Program

#include <bits/stdc++.h>
using namespace std;
int main(){
    vector<int> a={4,5,2,25},res(a.size()); stack<int> st;
    for(int i=a.size()-1;i>=0;i--){
        while(!st.empty() && st.top()<=a[i]) st.pop();
        res[i]=st.empty()?-1:st.top();
        st.push(a[i]);
    }
    for(int x:res) cout<<x<<" ";
}

C++ Output

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

JAVA Program

import java.util.*;
class Main{
    public static void main(String[] args){
        int[] a={4,5,2,25},res=new int[a.length];
        Stack<Integer> st=new Stack<>();
        for(int i=a.length-1;i>=0;i--){
            while(!st.isEmpty() && st.peek()<=a[i]) st.pop();
            res[i]=st.isEmpty()?-1:st.peek();
            st.push(a[i]);
        }
        for(int x:res) System.out.print(x+" ");
    }
}

JAVA Output

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

Python Program

a=[4,5,2,25]; res=[0]*len(a); st=[]
for i in range(len(a)-1,-1,-1):
    while st and st[-1]<=a[i]: st.pop()
    res[i]=-1 if not st else st[-1]
    st.append(a[i])
print(res)

Python Output

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

How It Works (Deep Dive)

Naive Approach

You might look at each element and search right until you have a larger number.

That's O(n²) in the worst case.

Example: For [4,5,2,25]:

4 → look right → finds 5

5 → look right → finds 25

2 → look right → finds 25

25 → no larger element → -1

But looking for all elements is inefficient when you can recycle work.

Optimized Stack-Based Approach (O(n))

We traverse the array from right to left and maintain a monotonic decreasing stack:

The stack contains only potential "next greater" candidates.

We pop off all elements that are less than or equal to the current element (since they will never be the NGE of anything to the left).

If the stack is empty after popping, NGE is -1.

Otherwise, the top of the stack is the NGE.

Push the current element onto the stack for later use.

Step-by-Step Example

Array: [4, 5, 2, 25]

We will monitor stack and result.

Begin: stack = []

i = 3 → element = 25

Stack is empty → NGE = -1

Push 25 → stack = [25]

i = 2 → element = 2

Stack top 25 > 2 → NGE = 25

Push 2 → stack = [25, 2]

i = 1 → element = 5

Pop 2 (2 ≤ 5) → stack = [25]

Top 25 > 5 → NGE = 25

Push 5 → stack = [25, 5]

i = 0 → element = 4

Top 5 > 4 → NGE = 5

Push 4 → stack = [25, 5, 4]

Result: [5, 25, 25, -1]

Time Complexity

Each element is pushed and popped at most once → O(n).

Space complexity = O(n) for the stack and result.

Real-World Uses

Stock span issues (determining the next higher stock price day).

Weather forecasting (determining the next warmer day).

Scheduling jobs (determining the next more costly or higher priority job).