Next Greater Element

by · June 9, 2020

“Next Greater Element” is a classic interview problem based on stack data structure. Here, we have given an array with ‘n’ elements. Our task is to print next greater element of each element of an array. If there is no greater element for any element in an array, simply print “-1” for that particular element.

Example:
Array: [12, 43, 11, 17, 78, 23].
Next Greater Element: [43, 78, 17, 78, -1, -1].
Array: [5, 4, 3, 2, 1].
Next Greater Element: [-1, -1, -1, -1, -1].

There are multiple ways to find the next greater element of every element of the array. Some of them are:

METHOD 1: Brute – Force Approach

The brute force approach of the following problem would be simply run two nested for loops and print next greater element for every element of an array. If no next greater element is found for any particular element of an array, simply print ‘-1’ for that element.

The time complexity of the following function is O(n^2).

C++ Program to find Next Greater Element of the Array is as follows:

#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[], int size)
{
    for(int i = 0 ; i < size ; i++)
    {
        cout<<arr[i]<<" ";
    }
}
void printNextGreater(int arr[], int size)
{
    for(int i = 0 ; i < size ; i++)
    {
        int print = 0;
        for(int j = i+1 ; j < size ; j++)
        {
        // Next Greater Element Condition
            if(arr[j] > arr[i])
            {
                cout<<arr[j] << " ";
                print = 1;
                break;
            }
        }
        // If No Greater Element is Found, print -1
        if(print == 0)
        cout<<"-1 ";
    }
}

int main()
{
    int arr[] = {12, 43, 11, 17, 78, 23};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"The Elements of an array are:\n";
    printArray(arr,size);
    cout<<"\nNext Greater Element of Every Element are:\n";
    printNextGreater(arr,size);
    return 0;
}


OUTPUT:
The Elements of the array are:
12 43 11 17 78 23
Next Greater Element of Every Element are:
43 78 17 78 -1 -1

METHOD 2: Stack – Based Approach

The steps to find next greater element using stack based approach are as follows:

  1. Initialize an empty integer stack and an array which will contain next greater element of every element.
  2. Push the index of very first element of an array into the stack.
  3. For the rest of the element, if the stack is empty or the element with top index of the stack is greater than the current element, then push the current element index into the stack.
  4. Else if the element with top index of the stack is smaller than the current element, then the current element will become next greater element of the top element of the stack.
  5. Keep popping from stack while popped index element is smaller than current element.
  6. Finally, push the current element index into the stack.
  7. Repeat steps from 3 to 6 until all the elements of an array are scanned.
  8. After that, for every remaining indexes present in stack, assign  -1 result with them.
  9. Print the next greater element array.

The time complexity to find the next greater element of every element using stack based approach is O(n).

C++ Program to find Next Greater Element of the Array is as follows:

#include<bits/stdc++.h>
using namespace std;
void printArray(int arr[], int size)
{
    for(int i = 0 ; i < size ; i++)
    {
        cout<<arr[i]<<" ";
    }
}
void printNextGreater(int arr[], int size)
{
    int nextGreater[size];
    stack <int> st;
    //Push the first index of the array,
    st.push(0);
    // For rest of the Elements,
    for(int i = 1 ; i < size ; i++)
    {
        // If Stack is empty
        if(st.empty())
        {
            st.push(i);
            continue;
        }
        // Else pop every smaller element index than current element from stack
        while(!st.empty() && arr[st.top()] < arr[i])
        {
            nextGreater[st.top()] = arr[i];
            st.pop();
        }
        // Push the current element index
        st.push(i);
    }
    //Other other element, assign -1 for them
    while(!st.empty())
    {
        nextGreater[st.top()] = -1;
        st.pop();
    }
    printArray(nextGreater,size);
}
int main()
{
    int arr[] = {12, 43, 11, 17, 78, 23};
    int size = sizeof(arr)/sizeof(arr[0]);
    cout<<"The Elements of an array are:\n";
    printArray(arr,size);
    cout<<"\nNext Greater Element of Every Element are:\n";
    printNextGreater(arr,size);
    return 0;
}


OUTPUT:
The Elements of the array are:
12 43 11 17 78 23
Next Greater Element of Every Element are:
43 78 17 78 -1 -1

Related Posts:

  1. Check whether given Parentheses String are Balanced Parentheses or Not.
  2. Find Minimum number of bracket reversals required to make an expression balanced.
  3. Implement Queue Using Two Stacks.
  4. Merge Overlapping Intervals using Stacks
  5. Implement Stack Using Linked List
  6. Largest Rectangular Area in Histogram
  7. Length of Longest Valid Substring
  8. Reverse a String using Stack
  9. Implement two stacks in a single array
  10. Print Bracket Number
  11. Next Greater Frequency Element
  12. Sort a Stack using Temporary Stack
  13. Find Most Frequent Character of the String.
  14. Check Anagram Strings.
  15. Check Whether Given String is Palindromic Anagram or Not.
  16. Check Whether Given String is Panagram or Not.
  17. Find First Non-Repeating Character of the String.
  18. Find Most Frequent Element of the Array.
  19. Find Pair in an Array with Given Sum.
  20. Find First Repeating Element of an Array.

Tags:

You may also like...