Brute force and optimised solution


#1
vector<int> Solution::prevSmaller(vector<int> &A) {
// this question in nearest smallest elelment to the left
vector<int> ans;
for(int i = A.size()-1;i>=0;i--){
    bool flag = false;
    for(int j=i-1;j>=0;j--){
        if(A[j]<A[i]){
            ans.push_back(A[j]);
            flag = true;
            break;
        }
    }
    if(flag == false){
        ans.push_back(-1);
    }
}`
reverse(ans.begin(),ans.end());
return ans;

}

the optimised approach using stack
vector Solution::prevSmaller(vector &A) {
// we will traverse from left to right and store the element in stack
stack s;
vectorans;
for(int i=0;i<A.size();i++){
// if stack is empty then we will have to push -1
if(s.empty()){
ans.push_back(-1);
}
else if(!s.empty() and s.top()<A[i]){
ans.push_back(s.top());
}
else if(!s.empty() and s.top()>=A[i]){
while(!s.empty() and s.top()>=A[i]){
s.pop();
}
if(s.empty()){
ans.push_back(-1);
}
else{
ans.push_back(s.top());
}
}
s.push(A[i]);
}
return ans;
}