Nearest Smaller Element

Using Stack

vector<int> Solution::prevSmaller(vector<int> &A) {
    stack<int> s;
    vector<int> res;
    
    for(const int &x: A) {
        while(!s.empty() && s.top() >= x) 
            s.pop();
            
        res.push_back(s.empty() ? -1 : s.top());
        s.push(x);
    }
    return res;
}

Time Complexity: $O(n)$

Space Complexity: $O(1)$

PreviousRedundant Braces NextFirst non-repeating character in a stream of characters

Last updated 2 years ago

Using Stack

vector<int> Solution::prevSmaller(vector<int> &A) {
    stack<int> s;
    vector<int> res;
    
    for(const int &x: A) {
        while(!s.empty() && s.top() >= x) 
            s.pop();
            
        res.push_back(s.empty() ? -1 : s.top());
        s.push(x);
    }
    return res;
}

Time Complexity:

O(n)

Space Complexity:

O(1)