Given an array a of integers of length n, find the nearest smaller number for every element such that the smaller element is on left side.If no small element present on the left print -1.
Example 1:
Input: n = 3 a = {1, 6, 2} Output: -1 1 1 Explaination: There is no number at the left of 1. Smaller number than 6 and 2 is 1.
Example 2:
Input: n = 6 a = {1, 5, 0, 3, 4, 5} Output: -1 1 -1 0 3 4 Explaination: Upto 3 it is easy to see the smaller numbers. But for 4 the smaller numbers are 1, 0 and 3. But among them 3 is closest. Similary for 5 it is 4.
I have written two codes for solving this problem, First one doesn't work for few test cases.. second works for everything, but I am not able to figure out in which case the first one will fail. Any leads please..
1.
vector<int> vect; stack<int> stk;
vect.push_back(-1);
for(int i=1; i<n; i++){
if(a[i-1]<a[i]){
stk.push(a[i-1]);
vect.push_back(a[i-1]);
}
else{
while(!stk.empty() && (stk.top()>a[i])){
stk.pop();
}
if(stk.empty())vect.push_back(-1);
else vect.push_back(stk.top());
}
}
stack<int> S;
vector<int> vect;
for (int i=0; i<n; i++)
{
while (!S.empty() && S.top() >= a[i])
S.pop();
if (S.empty())
vect.push_back(-1);
else
vect.push_back(S.top());
S.push(a[i]);
}