Problem Statement

Return the integar array G such that G[i] contains nearest smaller number than A[i].If no such element occurs G[i] should be -1.

For Example

`Input 1: A = [4, 5, 2, 10, 8] Output 1: G = [-1, 4, -1, 2, 2] Explaination 1: index 1: No element less than 4 in left of 4, G[1] = -1 index 2: A[1] is only element less than A[2], G[2] = A[1] index 3: No element less than 2 in left of 2, G[3] = -1 index 4: A[3] is nearest element which is less than A[4], G[4] = A[3] index 4: A[3] is nearest element which is less than A[5], G[5] = A[3]

Input 2: A = [3, 2, 1] Output 2: [-1, -1, -1] Explaination 2: index 1: No element less than 3 in left of 3, G[1] = -1 index 2: No element less than 2 in left of 2, G[2] = -1 index 3: No element less than 1 in left of 1, G[3] = -1`

Problem Link

Nearest Smaller Element - InterviewBit

Code

vector<int> Solution::prevSmaller(vector<int> &A) {

    int n = A.size();
    
    stack<int> s;
    vector<int> res(n,-1);
    **//Start from right if left min/max is required and vice versa**
    for(int i=n-1;i>=0;i--)
    {
        while(s.size()&&A[i]<A[s.top()])
        {
            res[s.top()] = A[i];
            s.pop();
        }
        s.push(i);

    }
    return res;
}