Next Greater Element

Last Updated on September 13, 2022 by Gokul Kannan

Problem statement

Given an array, consisting of n elements, find the next greater element of each element. The next greater element of any element is the first larger element to its right.

Input: Integer array of size of n.
Output: Integer array of size n.

Test cases:
Input:
[1, 4, 2, 17, 9, 12]

Output:
[4, 17, 17, -1, 12, -1]

Explanation:

• Output[0] = 4 because the next element greater than 1 is 4.
• Output[1] = 17 because the next element greater than 4 is 17.
• Output[2] = 17 because the next element greater than 2 is 4.
• Output[3] = -1 because there is no element greater than 17 to its right side.
• Output[4] = 12 because the next element greater than 2 is 12.
• Output[5] = -1 because there is no element on the right side of 12

Naive Approach – Brute Force

We will iterate each element of the given array and for each element we will check all the elements to its right.
The answer of any element will be the first element greater than itself. If we don’t find any greater element than the answer of that element will be -1.

Algorithm

1. Initialize an empty array
2. For each i in 0 to n:
    a. For each j in i + 1 to n: 
        If  arr[j] > f arr[i], then ans[i] = arr[j]
    b. If we does not found the greater element, then 
        ans[i] = -1
3. Return ans array.

Code Implementation:

import java.util.*;
class Prepbytes {
    // This function will find the next greater element for each element
    public static int[] nextGreaterElement(int arr[], int n)
    {
          int ans[] = new int[n];
	    for(int i = 0; i < n; i++){
	        boolean found = false;
	        for(int j = i + 1; j < n; j++){
	            if(arr[j]>arr[i]){
	                ans[i] = arr[j];
	                found = true;
	                break;
	            }
	        }
	        if(!found){
	            ans[i] = -1;
	        }
	    }
	    return ans;
    }
    public static void main(String[] args) {
        int arr[] = new int[]{1, 4, 2, 17, 9, 12};
        int ans[] = nextGreaterElement(arr, arr.length);
        for(int e : ans){
            System.out.print(e+" ");
        }
    }
}

Output:
4 17 17 -1 12 -1

Time complexity: O(n^2). It takes O(n) to find the next greater element of one element, and we have to find n elements. Hence, the time complexity will be O(n^2).

Space Complexity: O(n). The space required is only for the input and output array. The auxiliary space complexity is O(1).

Efficient Approach – Using Stack

The idea is to use the LIFO property of the stack data structure.The stack will be used to store the elements in a monotonically increasing order.

We will iterate every element in the given array. For each element, while the stack is not empty and the current element is greater than the top of the stack, we will keep removing the top of the stack. After the while loop terminates, there could be two possible cases:

Case 1: The stack is empty. If the stack is empty it means that there were no greater elements than the current element. Hence, we will set ans[i] as -1.

Case 2: We found an element greater than the current element. Then we will set ans[i] as the top of the stack.

Algorithm

1. Initialize an empty stack and an array.
2. Iterate i from 0 to n.
    a. While stack is not empty and the current element is
    greater than the top of the stack
        i. Remove the top the stack
    b. If the stack is empty, then it mean there is no next
    greater element for this element
        i. ans[i] =  -1.
    c. Otherwise, ans[i] = top of the stack
    d. Push the current element to the stack
3. Return ans array.

Code Implementation:

import java.util.Stack;
class Prepbytes {

    // This function will find the next greater element for each 
    // element
    public static int[] nextGreaterElement(int arr[], int n)
    {
          Stack<Integer> st = new Stack<>();
	    int ans[] = new int[n];
	    
	    // Iterate over the given array
	    for(int i = n - 1; i>= 0; i--){
	        
	        // While stack is not empty and the current
	        // element is greater than the top of the
	        // stack, keeping removing the top of the stack
	        while(!st.isEmpty() && arr[i] >= st.peek()){
	            st.pop();
	        }
	        
	        // If the stack is empty, then it mean there is no next greater
	        // element for this element
	        if(st.isEmpty()){
	            ans[i] = -1;
	        } 
	        // Otherwise, the top of the stack is the next greater
	        // element for this element
	        else {
	            ans[i] = st.peek();
	        }
	        
	        // Push the current element to the stack
	        st.push(arr[i]);
	    }
	    return ans;

    }
    
    public static void main(String[] args) {
        int arr[] = new int[]{1, 4, 2, 17, 9, 12};
        int ans[] = nextGreaterElement(arr, arr.length);
        for(int e : ans){
            System.out.print(e+" ");
        }
    }
}

Output:
4 17 17 -1 12 -1

Time complexity: O(n). We can observe that every element is pushed and removed from the stack only once. Hence, the total operations being performed is 2n and O(2n) = O(n) because we don’t consider constant terms during asymptotic analysis of time complexity.

Space Complexity: O(n). O(n) space is required for the input and output array. The auxiliary space complexity is O(n) as we are using a stack. At any point of time the stack can contain at most n elements..

This article tried to discuss the most efficient way to find the next greater element. Hope this blog helps you understand and solve the problem. To practice more problems you can check out MYCODE | Competitive Programming at Prepbytes..