Next Smaller Element

The problem, simply

You get an array of numbers. For each number, look to its right and find the first number that is strictly smaller. That is its next smaller element. If there is none, the answer for that spot is -1. Give back all the answers as an array.

A story to remember it

Picture it

Examples

Way 1: the simple way

For each spot i, walk right with j until you find something smaller.

1. Set every answer to -1.
2. For each i, for j from i + 1 to the end: if arr[j] < arr[i], the answer is arr[j]. Stop.

import java.util.*;

class Solution {
    public int[] nextSmaller(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[i]) {     // the first smaller one to the right
                    ans[i] = arr[j];
                    break;
                }
            }
        }
        return ans;
    }
}

How long it takes: for a line that only goes up, every i walks to the end, O(n^2). Extra room: only the answer array, O(1) extra.

Way 2: the clever way

Walk from right to left and keep a stack of numbers that could still be an answer. The stack always gets bigger from bottom to top.

1. For each i from the right end to the left:
2. Pop every number on the stack that is greater than or equal to arr[i]. It can never be the answer for anyone to the left, because arr[i] is closer and not bigger.
3. If the stack is empty, the answer is -1. Otherwise the top is the answer.
4. Push arr[i].

import java.util.*;

class Solution {
    public int[] nextSmaller(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();     // gets bigger from bottom to top
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= arr[i]) {
                stack.pop();                           // hidden behind arr[i] from now on
            }
            ans[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(arr[i]);
        }
        return ans;
    }
}

How long it takes: every number is pushed once and popped at most once, so all the popping together is at most n steps, O(n). Extra room: the stack can hold every number when the array keeps going down, like [5, 4, 3, 2], O(n).

Another way: left to right, answers handed out

You can also walk left to right and keep a stack of positions that are still waiting for an answer. When arr[i] is smaller than the number at the top position, arr[i] is that position's answer. Pop it and keep checking.

import java.util.*;

class Solution {
    public int[] nextSmaller(int[] arr) {
        int n = arr.length;
        int[] ans = new int[n];
        Arrays.fill(ans, -1);                          // whoever never gets an answer keeps -1
        Deque<Integer> waiting = new ArrayDeque<>();   // positions still waiting
        for (int i = 0; i < n; i++) {
            while (!waiting.isEmpty() && arr[waiting.peek()] > arr[i]) {
                ans[waiting.pop()] = arr[i];           // arr[i] is their first smaller one
            }
            waiting.push(i);
        }
        return ans;
    }
}

Same O(n) time and O(n) room. This version is handy when you need the position of the answer, not only its value.

Watch out for

• Storing values when you later need distances or positions. If the follow up asks "how far away", store indices in the stack instead.
• Mixing up the direction. "Next" means to the right. "Previous smaller" means to the left: walk left to right with the same pop rule.
• Forgetting to fill -1 for kids left on the stack in the left to right version.

What interviewers ask next

• Next greater element: flip the comparison. Pop while top <= arr[i].
• Circular array: the right end wraps around to the start. Walk i from 2n - 1 down to 0 and use arr[i % n].
• Stock span: how many days in a row, ending today, had a price not higher than today? That is a previous greater element problem with indices.
• Largest rectangle in a histogram uses both the previous smaller and the next smaller element of every bar.
• Sum of the minimums of all subarrays: each number is the minimum of (i - prevSmaller) * (nextSmaller - i) subarrays. Use strict on one side and not strict on the other so equal numbers are counted once.

Remember this

Grown-up words: the list of kids you can still see is a monotonic stack, "the first smaller one to the right" is the next smaller element, and "each item pushed and popped once" is amortized O(1) per step.