# Next Greater Element

“** 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; }

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

**METHOD 2: Stack – Based Approach**

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

- Initialize an empty integer stack and an array which will contain next greater element of every element.
- Push the index of very first element of an array into the stack.
- 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.
- 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.
- Keep popping from stack while popped index element is smaller than current element.
- Finally, push the current element index into the stack.
- Repeat steps from 3 to 6 until all the elements of an array are scanned.
- After that, for every remaining indexes present in stack, assign -1 result with them.
- 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; }

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

**Related Posts:**

**Check whether given Parentheses String are Balanced Parentheses or Not.****Find Minimum number of bracket reversals required to make an expression balanced.****Implement Queue Using Two Stacks.****Merge Overlapping Intervals using Stacks****Implement Stack Using Linked List****Largest Rectangular Area in Histogram****Length of Longest Valid Substring****Reverse a String using Stack****Implement two stacks in a single array****Print Bracket Number****Next Greater Frequency Element****Sort a Stack using Temporary Stack****Infix to Postfix Conversion****Infix to Prefix Conversion****Prefix to Infix Conversion****Prefix to Postfix Conversion****Postfix to Infix Conversion****Postfix to Prefix Conversion****Program to find equilibrium index of an Array.****Program to find majority element of an Array.**