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

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[]) 

        // 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[])
            right[i] = A[];

        // push the current element in the stack    


    // return the final array 

    return right;


It would be way better to understand if you make

A[] ---->;

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


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.