Hello Guys, in this article we will provide you the code of the Nearest Greater to the Left. We will solve this problem with the use of the Stack of Nearest Greater to Left.
This is the variation of the Next Largest Element.
Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?
The idea is to store the elements for which we have to find the next greater element in a stack and while traversing the array, if we find a greater element, we will pair it with the elements from the stack till the top element of the stack is less than the current element.
Steps to Solve the Problem
- Push the first element to stack.
- Pick the rest of the elements one by one and follow the following steps in the loop.
- Mark the current element as next.
- If the stack is not empty, compare top most elements of the stack with the next.
- If the next is greater than the top element, Pop the element from the stack. next is the next greater element for the popped element.
- Keep popping from the stack while the popped element is smaller than the next. next becomes the next greater element for all such popped elements.
- Finally, push the next in the stack.
- After the loop in step 2 is over, pop all the elements from the stack and print -1 as the next element for them.
Implementation of the steps
#include <bits/stdc++.h>
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
void printNGE(int arr[], int n)
{
stack<int> s;
vector<int> v;
for (int i=0;i<n;i++){
if(s.size()==0){
v.push_back(-1);
}
else if (s.size()>0 && s.top()>arr[i]){
v.push_back(s.top());
}
else if(s.size()>0 && s.top()<=arr[i]){
while(s.size()>0 && s.top()<=arr[i]){
s.pop();
}
if(s.size()==0){
v.push_back(-1);
}
else
{ v.push_back(s.top());
}
}
s.push(arr[i]);
}
//reverse(v.begin(), v.end());
for (int i = 0; i < n; i++) {
cout << v[i] << " ";
}
}
int main()
{
int arr[] = {4, 5, 2, 10, 8};
int n = sizeof(arr) / sizeof(arr[0]);
printNGE(arr, n);
return 0;
}
/// contributed by Iresh SinglaOutput
-1 -1 5 -1 10
Time Complexity: O(N)
Auxiliary Space: O(N)