Home » Technical Interview Questions » Array Interview Questions » Next Greater Element in an Array

Next Greater Element in an Array


Reading Time - 3 mins

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

Input

9

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

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.

READ  Infix to Postfix

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;
}
9
4 5 8 1 3 7 11 13 2
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

Complexity Analysis for Next Greater Element in an Array

Time Complexity

O(N) where n is the number of elements present in the array. Here we visit the value of the array exactly one time. This approach leads us to linear time complexity.

Space Complexity

O(N) because the maximum size of the stack goes upto O(n).

References

Array Interview Questions
Graph Interview Questions
LinkedList Interview Questions
String Interview Questions
Tree Interview Questions