# 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 Arrayis 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);
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 Arrayis 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);
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: