Next Smaller Element

Medium

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: []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}