C++ | O(n) | Using a stack


#1
vector<int> Solution::prevSmaller(vector<int> &A) {
    if(A.size() == 0) return {};
    if(A.size() == 1) return {-1};
    
    stack<pair<int,int>> s;
    s.push({A[A.size()-1],A.size()-1});
    for(int i=A.size()-2;i>=0;i--){
        while(!s.empty() && A[i] < s.top().first){
            A[s.top().second] = A[i];
            s.pop();
        }
        s.push({A[i],i});
    }
    
    while(!s.empty()){
        A[s.top().second] = -1;
        s.pop();
    }
    return A;
}