Next Smaller Element

Practice Link

ThGiven an array, find the nearest smaller element G[i] for every element A[i] in the array such that the element has an index smaller than i.

More formally,

• G[i] for an element A[i] = an element A[j] such that
• j is maximum possible AND
• j < i AND
• A[j] < A[i] Elements for which no smaller element exist, consider next smaller element as -1.

Intiution#

• We maintain a stack called monotonic stack (increasing)

Solution - Monotonic Stack#

Traverse the array left-to-right and maintain a monotonically increasing stack of values. Before each element is processed, pop all stack entries that are greater than or equal to the current element — those cannot be the "previous smaller" for any future element to the right. The top of the stack after popping is the nearest smaller element to the left of A[i]; if the stack is empty, no smaller element exists and the answer is -1. Each element is pushed and popped at most once, giving O(n) time overall.

vector<int> Solution::prevSmaller(vector<int> &A) {
    vector<int> ans(A.size(), -1);
    stack<int> stk;

    for(int i=0;i<A.size();i++)
    {
        while(!stk.empty() && stk.top() >= A[i])
            stk.pop();
        if(!stk.empty())
            ans[i] = stk.top();
        stk.push(A[i]);
    }
    return ans;
}

Time Complexity: O(n)

Space Complexity: O(n)