& Code
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).
Report Error/ Suggestion