Stack Boundaries — Nearest Greater / Smaller

For each position, the nearest interesting neighbor to the left/right is often found by popping “useless” indices from a stack.

Try this in Python

def nearest_smaller_left(nums: list[int]) -> list[int | None]:
    st: list[int] = []
    out: list[int | None] = []
    for i, x in enumerate(nums):
        while st and nums[st[-1]] >= x:
            st.pop()
        out.append(None if not st else nums[st[-1]])
        st.append(i)
    return out


print(nearest_smaller_left([3, 1, 2, 4]))

Key takeaways

• Monotonicity tells you when to discard candidates.
• Store indices when you need spans or rectangles later.
• Classic bridge to histogram and monotone stack lessons.