Easy O(n) solution using stacks you would love the approach


#1
vector<int> Solution::prevSmaller(vector<int> &arr) {
int n = arr.size();
vector<int>ans;
    stack<long long>s;
    ans.push_back(-1);
    s.push(arr[0]);
    for(long long i=1;i<n;i++)
    {
        long long k = s.top();
        
        if(arr[i]>k)
        {
            ans.push_back(k);
            s.push(arr[i]);
        }
        else
        {
            s.pop();
            while(!s.empty())
            {
                long long l = s.top();
                if(arr[i]>l)
                {
                    ans.push_back(l);
                    s.push(arr[i]);
                    break;
                }
                else 
                s.pop();
            }
            
            if(s.size()==0){
            ans.push_back(-1);
            s.push(arr[i]);
            }
        }
    }
    
  //  reverse(ans.begin(),ans.end());
    
    return ans;

}