Next Greater Element

Level - Medium

Statement

Given an array arr[] of size N having distinct elements, the task is to find the next greater element for each element of the array.

What is next greater element ?

Next greater element of an element in the array is, the first greater element on right hand side.

Example:

Input: N = 5, arr[]=[6 8 0 1 3]

Output:
8 -1 1 3 -1

Explanation:

6 -> 8
8 -> -1 // as no element is greater then 8 on right hand side
0 -> 1
1 -> 3
3-> -1

You can try this at:

• https://practice.geeksforgeeks.org/problems/next-larger-element-1587115620/1

Brute Force Approach

• just loop though all the elements in the array and find the next greater element by using nested loop.

int[] res; // initially all the elements in the res array is -1
for(int i=0;i<n;i++){
    for(int j=i+1;j<n;j++){
        if(arr[j] > arr[i]){
            res[i] = arr[j];
            break;
        }
    }
}
res[n-1] = -1;// for last element
return res; // the resultant array

Time Complexity:

O(N^2)

Space Complexity:

O(N)

Optimal Approach

note

now we will first see the working of an algorithm and then we will jump on intution

• create an empty stack

• iterate from last of the array and on each step perform below tasks:

  • run a while loop if this condition satisfies stack.isEmpty()==false && arr[i]>=stack.peek() then perform stack.pop()

  • now the next greater element for arr[i] is stack.peek(), so if(stack.isEmpty==false)res[i] = stack.peek() else res[i] = -1

  • insert arr[i] into the stack, so stack.push(arr[i])

• at the end we have res[] as a resultant array

Dry Run

Intution

Java

public static long[] nextLargerElement(long[] arr, int n) {
    long[] res = new long[n];
    Stack < Long > st = new Stack < > ();

    for (int i = n - 1; i >= 0; i--) {
        // maintain the increasing order from bottom to top in the stack
        while (!st.isEmpty() && st.peek() <= arr[i]) {
            st.pop();
        }

        // update the result
        if (st.isEmpty()) res[i] = -1;
        else res[i] = st.peek();
        
        // push the current element to the stack      
        st.push(arr[i]);
    }
    return res;
}

Cpp

 vector <long long> nextLargerElement(vector < long long > arr, int n) {
   // Your code here
   vector < long long > res(n);
   stack < long long > st;

   for (int i = n - 1; i >= 0; i--) {
     // maintain the increasing order from bottom to top in the stack
     while (!st.empty() && st.top() <= arr[i]) {
       st.pop();
     }
     if (st.empty()) res[i] = -1;
     else res[i] = st.top();

     // push the current element to the stack      
     st.push(arr[i]);
   }
   return res;
 }

Python

def nextLargerElement(self, arr, n):
    # code here
    res = [0] * n
    st = []

    for i in range(n - 1, -1, -1):
        # maintain the increasing order from bottom to top in the stack
        while len(st) != 0 and st[-1] <= arr[i]:
            st.pop()
        if len(st) == 0:
            res[i] = -1
        else:
            res[i] = st[-1]

        # push the current element to the stack
        st.append(arr[i])

    return res

Time Complexity:

O(N)

Space Complexity:

O(N)