What signals in a problem statement indicate the Next / previous smaller sub-pattern?

"first price to the right that is lower or equal"; "next smaller element"; "remove k digits so the number is smallest"; "smallest subsequence / remove duplicate letters"

Next / previous smaller (Monotonic Stack Sub-pattern)

Q: What makes Next / previous smaller different from other sub-patterns?

**Final Prices** pops while `top ≥ x` (≤ counts). **Next Smaller Element** shows the other direction: scan right-to-left, throw away candidates that are `≥` the current value, and the top is the answer. **Remove K Digits** and **Remove Duplicate Letters** build the answer on the stack: a smaller digit/letter pops bigger ones before it — but only while you're allowed (`k > 0`, or the popped letter appears again later).

Increasing stack. A smaller arrival pops every bigger waiting element. The same shape powers greedy "make it as small as possible" questions, where the stack is the answer being built.

Signals in the problem statement

›
"first price to the right that is lower or equal"
›
"next smaller element"
›
"remove k digits so the number is smallest"
›
"smallest subsequence / remove duplicate letters"

What makes it different

Final Prices pops while top ≥ x (≤ counts). Next Smaller Element shows the other direction: scan right-to-left, throw away candidates that are ≥ the current value, and the top is the answer. Remove K Digits and Remove Duplicate Letters build the answer on the stack: a smaller digit/letter pops bigger ones before it — but only while you're allowed (k > 0, or the popped letter appears again later).

Questions

ordered from “learn the idea” to “recognise it without help”

1
Final Prices With a Special Discount in a Shop
Basic Anchor·LeetCode #1475
WalkthroughEasy
2
Next Smaller Element
Basic Reinforcement·GeeksforGeeks
WalkthroughMedium
3
Remove K Digits
Pattern Transfer·LeetCode #402
WalkthroughMedium
4
Remove Duplicate Letters
Interview-Level·LeetCode #316
WalkthroughMedium

Template

next-greater-template.cpp

// Next greater element to the right; -1 if none. Decreasing stack of indices.
vector<int> nextGreater(vector<int>& a) {
    int n = a.size();
    vector<int> ans(n, -1);                          // leftovers keep -1
    stack<int> st;                                   // indices; values decrease bottom → top
    for (int i = 0; i < n; i++) {
        while (!st.empty() && a[st.top()] < a[i]) {  // a[i] beats the waiting top
            ans[st.top()] = a[i];                    // answer written on POP
            st.pop();
        }
        st.push(i);                                  // a[i] now waits for its own answer
    }
    return ans;
}

Remember this · Monotonic Stack

Trigger

Next/previous greater or smaller element, spans, histogram areas, "for each element, how far does it dominate?"

Think

When a new element arrives, which older elements can never be the answer again?

Key question

Is my stack increasing or decreasing, and what do I record when I pop?

Next / previous greater Contribution / boundaries