Next Smaller Element
Problem
For each element, find the first element to its right that is strictly smaller. Use −1 when there is none.
Example 1
Input: [4, 8, 5, 2, 25] Output: [2, 5, 2, -1, -1]
Also asked as: Next Smaller Element
Test cases
Case 1
Input: [4,8,5,2,25] Expected: [2,5,2,-1,-1]
Case 2
Input: [3,2,1] Expected: [2,1,-1]
Case 3
Input: [1,2,3] Expected: [-1,-1,-1]
Case 4
Input: [] Expected: []
View solutionHide solution1 approach
1. Monotonic increasing stack
Time O(n)Space O(n)
Scan; pop while the stack top is greater than the current value — the current value is those elements’ next smaller.
function nextSmaller(a) { const res = Array(a.length).fill(-1); const st = []; for (let i = 0; i < a.length; i++) { while (st.length && a[st[st.length - 1]] > a[i]) res[st.pop()] = a[i]; st.push(i); } return res;}