Next Smaller Element
MediumIncreasing stack instead
Problem
For each element, find the next element to its right that is smaller, or -1 if none.
Keep a stack of items waiting for something smaller; a small value resolves everyone bigger behind it.
The idea
The same monotonic sweep with the comparison flipped: pop while the stack top is larger than the current element, because that element is the popped one's next smaller neighbour.
The trick
- Increasing stack for next-smaller, decreasing for next-greater.
- Store indices when you need the distance, values when you need the number.
4
8
5
2
25
0
1
2
3
4
Step 1 of 8. Brute force: for each element, scan right for the next smaller one. Values: 4, 8, 5, 2, 25.
1/8
Brute force
timeO(n²)spaceO(1)
Scan right.
1for (let i = 0; i < n; i++)2 for (let j = i + 1; j < n; j++)3 if (nums[j] < nums[i]) { res[i] = nums[j]; break; }4return res;Input
- array
- [4, 8, 5, 2, 25]
Memory
- i
- —
- j
- —
Output
- done
- —
Check yourself
3 quick questions about this walkthrough. A wrong answer costs nothing.
Examples
Example 1
- Input:
- nums = [4, 8, 5, 2, 25]
- Output:
- [2, 5, 2, -1, -1]
- Explanation:
- Each element's next smaller to the right.
Example 2
- Input:
- nums = [1, 2, 3]
- Output:
- [-1, -1, -1]
- Explanation:
- Increasing → all -1.
Example 3
- Input:
- nums = [3, 2, 1]
- Output:
- [2, 1, -1]
- Explanation:
- Each sees the next smaller neighbour.
Practice this problem:GeeksforGeeks(opens in a new tab)
Finished the walkthrough? Add it to your streak.