In this article, we will provide you with the solution of Next Smaller Element also known as Next Smaller Element in Left using Stack in C++. This is a famous problem solved using Stack in Data Structures and Algorithms.
The idea is to store the elements for which we have to find the next smaller element in a stack and while traversing the array, if we find a smaller element, we will pair it with the elements from the stack till the top element of the stack is more than the current element.
Looking for comprehensive study materials on Python, Data Structures and Algorithms (DSA), Object-Oriented Programming (OOPs), Java, Software Testing, and more?
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, then compare next with the stack top. If the next is smaller than the top then next is the NSE for the top. Keep popping from the stack while the top is greater than the next. next becomes the NSE for all such popped elements
- Push next into 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 4 -1 2 2
Time Complexity: O(N)
As we use only a single for loop and all the elements in the stack are pushed and popped at most once.
Auxiliary Space: O(N)
As extra space is used for storing the elements of the stack.