Find The Next Greater Element

Introduction

 
In this article, you will learn how to find every element's next greater element.
 

Problem Statement 

 
Given an array, for each element, find the next or element's right greater element. If there is no greater element, then set the value to -1. Here is one example, array [4, 2, 5, 9, 2, 3] would result in [5, 5, 9, -1, 3, -1].
 

Approach 1

 
The most naive way to solve this problem would be by using nested loops, one over every element, and then loop over all elements to its right. If we find a greater element, then we store it and move on or else we store -1.
 
Time Complexity - O(N^2)
Space Complexity - O(1).
 
It is a pretty slow algorithm since every element potentially has to visit every element to the right. But the algorithm doesn't use any extra space. Here's a sample code in C# that demonstrates this algorithm:
  1. class Program  
  2. {  
  3.     static void Main(string[] args)  
  4.     {  
  5.         int[] array = new int[] { 4, 2, 5, 9, 2, 3 };  
  6.         int[] result = Approach1(array);  
  7.         //result is [ 5, 5, 9, -1, 3, -1 ]    
  8.     }  
  9.     static int[] Approach1(int[] array)  
  10.     {  
  11.         int[] result = new int[array.Length];  
  12.         for (int i = 0; i < array.Length; i++)  
  13.         {  
  14.             //firstly assume the element has no next greater element  
  15.             result[i] = -1;  
  16.   
  17.             //find next greater element by iterating over the rest  
  18.             for (int j = i + 1; j < array.Length; j++)  
  19.             {  
  20.                 //found the next greater element  
  21.                 if (array[j] > array[i])  
  22.                 {  
  23.                     result[i] = array[j];  
  24.                     break;  
  25.                 }  
  26.             }  
  27.         }  
  28.         return result;  
  29.     }  
  30. }  

Approach 2

 
This approach needs a stack to keep the index of the elements that don't have their next greater elements. In this solution, we visit every element to check whether the value of the current element is greater than the element on the top of the stack.
 
Time Complexity - O(N)
Space Complexity - O(N).
 
It is fast because we visit each element once. In the worst case, we have to put all elements onto the stack using up a lot of extra space. A pseudocode illustrating this solution is shown below using C#:
  1. class Program  
  2. {  
  3.     static void Main(string[] args)  
  4.     {  
  5.         int[] array = new int[] { 4, 2, 5, 9, 2, 3 };  
  6.         int[] result = Approach2(array);  
  7.         //result is [ 5, 5, 9, -1, 3, -1 ]    
  8.     }  
  9.     static int[] Approach2(int[] array)  
  10.     {  
  11.         Stack<int> nextGreaterIndex = new Stack<int>();  
  12.         int[] result = new int[array.Length];  
  13.         for (int i = 0; i < array.Length; i++)  
  14.         {  
  15.             //check if this element has any next greater element  
  16.             while (nextGreaterIndex.Count > 0)  
  17.             {  
  18.                 if (array[i] > array[nextGreaterIndex.Peek()])  
  19.                 {  
  20.                     result[nextGreaterIndex.Peek()] = array[i];  
  21.                     nextGreaterIndex.Pop();  
  22.                 }  
  23.                 else  
  24.                     break;  
  25.             }  
  26.             nextGreaterIndex.Push(i);  
  27.         }  
  28.   
  29.         //all elements left will have no next greater element  
  30.         while (nextGreaterIndex.Count > 0)  
  31.         {  
  32.             result[nextGreaterIndex.Peek()] = -1;  
  33.             nextGreaterIndex.Pop();  
  34.         }  
  35.         return result;  
  36.     }  
  37. }  

Approach 3

 
This solution is very similar to the above approach 2. The only difference is that we will visit the elements in reverse order. The reason is to have a greater element in the stack for the current element. The rest of with time and space complexities are the same as in approach 2. Below is a code sample for this approach in C#:  
  1. class Program  
  2. {  
  3.     static void Main(string[] args)  
  4.     {  
  5.         int[] array = new int[] { 4, 2, 5, 9, 2, 3 };  
  6.         int[] result = Approach3(array);  
  7.         //result is [ 5, 5, 9, -1, 3, -1 ]    
  8.     }  
  9.     static int[] Approach3(int[] array)  
  10.     {  
  11.         Stack<int> nextGreaterIndex = new Stack<int>();  
  12.         int[] result = new int[array.Length];  
  13.   
  14.         //reverse iteration    
  15.         for (int i = array.Length - 1; i >= 0; i--)  
  16.         {  
  17.             //pop untill the greater element   
  18.             while (nextGreaterIndex.Count > 0 && array[nextGreaterIndex.Peek()] <= array[i])  
  19.                 nextGreaterIndex.Pop();  
  20.   
  21.             //assign result with the top element of the stack  
  22.             result[i] = nextGreaterIndex.Count > 0 ? array[nextGreaterIndex.Peek()] : -1;  
  23.   
  24.             nextGreaterIndex.Push(i);  
  25.         }  
  26.         return result;  
  27.     }  
  28. }