# Next Greater Element

Written By -

Given: An array, we have to print the next greater element for each element. The Next greater Element for an element p is the first greater element on the right side of p in array. Elements for which there is no greater element, we consider next greater element as -1.

Example:

Input array: { 37, 23, 64, 10, 25, 7 }
Output:
Next greater element for 37     = 64
Next greater element for 23     = 25
Next greater element for 64     = -1
Next greater element for 10     = 23
Next greater element for 25     = 37
Next greater element for  7      = 10

### # Brute Force Approach

Code:

``````#include <iostream>

// prints NGE for all elements of array[]

void nextgren(int array[], int size)

{
int next;

for (int i = 0; i < size; i++)

{

next = -1;

for (int j = i + 1; j < size; j++)

{

if (array[i] < array[j])

{

next = array[j];

break;
}
}

std::cout << "Next greater element for " << array[i] << " = " << next << std::endl;
}
}

// Driver Code

int main()

{

int array[] = { 5, 4, 7, 15 };

int size = sizeof(array) / sizeof(array[0]);

nextgren(array, size);

return 0;

}``````

Time Complexity: O(n2).

### # Optimised Approach(Using Stack)

Code:

``````// C++ program to find next greater element using stack
#include <bits/stdc++.h>

// prints NGE for all elements of array

void nextgren(int array[], int size)

{

std::stack<int> stck;

// push first element to stck

stck.push(array[0]);

// iterating for next elements

for (int i = 1; i < size; i++)

{

if (stck.empty())

{

stck.push(array[i]);

continue;
}

/*if stck is not empty, then pop an element from stck.

If the popped element is smaller than next, then
1) print the element and next
2) keep popping while elements are smaller and stck is not empty */

while ((stck.empty() == false) && (stck.top() < array[i]))

{

std::cout << "Next greater element for " << stck.top() << " = " << array[i] << std::endl;

stck.pop();
}

// push next to stck so we can find next greater for it

stck.push(array[i]);
}

/*After iteration is over, the remaining

elements in stck do not have the next greater

element, so we print -1 for them */

while (stck.empty() == false)

{

std::cout << stck.top() << " --> " << -1 << " (No greater element in given input) " << std::endl;

stck.pop();
}
}

// Driver code

int main()

{

int array[] = { 6, 10, 12, 9 };

int size = sizeof(array) / sizeof(array[0]);

nextgren(array, size);

return 0;

}``````

Time Complexity: O(n).

Related Posts:

Online Compilers