Readable O(n) solution using stacks in C++ (with comments)


#1
vector<int> Solution::prevSmaller(vector<int> &A) 
{
    int n = A.size();
    vector<int> right(n, -1); // create the answer list and initialize all of it's values as -1
    stack<int> s; // create a stack
    
    for(int i = 0; i<n; i++)
    {
        // if the stack is not empty and the current value is less than the value on top of the stack, we pop 
        // it out because we won't be going beyond the current minimum point
      
        while(!s.empty() && A[i] <= A[s.top()]) 
            s.pop();

        // if the value is greater than preceding value, put the value which is at the top of the stack at the 
        //position of the current element

        if(!s.empty() && A[i] > A[s.top()])
            right[i] = A[s.top()];

        // push the current element in the stack    

        s.push(i);
    }

    // return the final array 

    return right;
}

#2

It would be way better to understand if you make

A[s.top()] ----> s.top();

s.push(i) ----> s.push(A[i]);


#3

Yes, storing the element is way more intuitive but storing the index comes in handy, not only in this problem but in others too, that’s why I have chosen to store index over the value. Storing value was my first thought as well.