Next Greater Element in an Array

Problem Statement

Given an array, we will find the next greater element of 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.

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

Example

9
4 5 8 1 3 7 11 13

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

Approach for Next Greater Element in an Array

This problem can be solved by using a stack. Here we traverse the array from the end and performing some operation on the stack. In the worst case, the size of the stack here reach up to N.

Algorithm

1. If the stack is empty or the current element is larger than the 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 the 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 the array is reached.

Implementation

C++ Program for Next Greater Element in an Array

#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 N;
  cin>>N;
  int arr[N];
  for(int i=0;i<N;i++)
  {
      cin>>arr[i];
  }
  findNGEs(arr,N);
  return 0;
}

import java.util.Scanner;
import java.util.Stack;
class sum
{
    public static void findNGEs(int arr[],int N)
    {
      System.out.print("The next Greater element of "+arr[N-1] +" is -1\n");
      Stack<Integer> S = new Stack<Integer>();
      S.push(arr[N-1]);
      for(int i=N-2;i>=0;i--)
      {
        while(!S.empty() && (arr[i] > (int) S.peek())) //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
        {
            System.out.print("The next greater element of "+arr[i]+" is -1\n");
        }
        else  //if stack not empty then top element is the next greater element
        {
            System.out.print("The next greater element of "+arr[i]+" is " + (int) S.peek()+"\n");
        }
        S.push(arr[i]);
      }
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        findNGEs(a,n);
    }
}

5
3 5 1 7 2

The next Greater element of 2 is -1
The next greater element of 7 is -1
The next greater element of 1 is 7
The next greater element of 5 is 7
The next greater element of 3 is 5