Next greater element for all the elements in the array

Given an array, we will find the next greater element of the each element in the array. If there is no next greater element for that element then we will print -1, else we will print that element.

Next greater element is the element that is greater and present on the right side of that element

Input : arr[] = {4,5,8,1,3,7,11,13,2}

Output :
    The next Greater element of 2 is -1
    The next greater element of 13 is -1
    The next greater element of 11 is 13
    The next greater element of 7 is 11
    The next greater element of 3 is 7
    The next greater element of 1 is 3
    The next greater element of 8 is 11
    The next greater element of 5 is 8
    The next greater element of 4 is 5

ALGORITHM

TIME COMPLEXITY – O(N)
SPACE COMPLEXITY – O(N)

This problem can be solved by using a stack.

We traverse the array from the end.

1. If the stack is empty or the current element is larger than top element of the stack, then push the current element on the stack and print the next greater element as -1.
2. If the current element is smaller than top element of the stack, then for this the next greater element is the top element of the stack.
3. While stack is not empty and the current element is greater than the stack top element. Keep poping elements from the stack Iterating above steps, Print the greater element if found else print -1. Push the current element on to the stack
4. Repeat steps 1 and 2 till the start  index of array is reached.

So,

-1   54   -1  - 1 -1 is the answer.

C++ Program

#include<bits/stdc++.h>
using namespace std;

void findNGEs(int arr[],int N)
{
	cout << "The next Greater element of "<<arr[N-1] <<" is -1\n";
	
	stack<int> S;
	S.push(arr[N-1]);
	
	for(int i=N-2;i>=0;i--)
	{
		
		while(!S.empty() and arr[i] > S.top()) //If array element is greater than top element then keep i popping
		{
			S.pop();
		}	
		
		if(S.empty()) //if stack is empty means no greater element
			{
				cout<<"The next greater element of "<<arr[i]<<" is -1\n";
				
			}
		else  //if stack not empty then top element is the next greater element
			{
				cout<<"The next greater element of "<<arr[i]<<" is " << S.top()<<"\n";
			}
		S.push(arr[i]);
	}
	

}

int main()
{
	int arr[] = {4,5,8,1,3,7,11,13,2};
	int N = sizeof(arr)/sizeof(arr[0]);	
	findNGEs(arr,N);

	return 0;
}
Try It


Next > < Prev
Scroll to Top