Skip to content

Nearest Smaller Elements

For each position in an array, find the nearest index to the left (or right) where the value is strictly smaller (or larger). A monotonic stack yields \(O(n)\) time—each index is pushed and popped at most once.

Nearest smaller to the left

For each i, want largest j < i with a[j] < a[i] (or -1 if none).

#include <vector>
#include <stack>
using namespace std;

// prevSmaller[i] = index j < i with a[j] < a[i], closest such j; -1 if none
vector<int> nearestSmallerLeft(const vector<int>& a) {
    int n = (int)a.size();
    vector<int> prevSmaller(n, -1);
    stack<int> st; // indices, values a[st] strictly increasing from bottom to top
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        if (!st.empty()) prevSmaller[i] = st.top();
        st.push(i);
    }
    return prevSmaller;
}

Use > instead of >= in the pop condition if you need strictly smaller on both sides without collapsing equal values—statement-dependent.

Nearest smaller to the right

Scan right to left, or one pass with symmetric logic:

vector<int> nearestSmallerRight(const vector<int>& a) {
    int n = (int)a.size();
    vector<int> nextSmaller(n, n);
    stack<int> st;
    for (int i = n - 1; i >= 0; i--) {
        while (!st.empty() && a[st.top()] >= a[i]) st.pop();
        if (!st.empty()) nextSmaller[i] = st.top();
        st.push(i);
    }
    return nextSmaller;
}

(n as sentinel means “no smaller to the right.”)

Nearest greater

Flip comparisons: pop while a[st.top()] <= a[i] for strictly greater neighbor patterns.