Stack boundaries — nearest greater/smaller

ஒவ்வொரு index-க்கும் அருகில் neighbor — useless indices pop.

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

• Monotone — candidates நீக்கம்.
• Indices — span/histogram.
• Monotonic stack-க்கு பாலம்.