☕ DSA Java Articles

Topics › Stacks and Queues › Monotonic Stack/Queue Problems [VVV. Imp]

Next Smaller Element

Medium TUF ID 768 A2ZSDE

Java source ↗ Edit this article ↗

Problem

Given an array arr of n integers, find for every index i its next smaller element: the first element to the right of i that is strictly smaller than arr[i]. If there is none, the answer for i is -1. Return the answers as an array of length n.

Constraints: 1 ≤ n ≤ 10^5, values fit in a 32-bit int.

Some versions of this problem, such as InterviewBit’s “Nearest Smaller Element”, ask instead for the nearest smaller element on the left. The same technique solves it by scanning in the other direction; that variant is covered after the main solution.

Example 1

arr    = [4, 8, 5, 2, 25]
answer = [2, 5, 2, -1, -1]     // 4 skips 8 and 5 (both bigger) and stops at 2

Example 2

arr    = [13, 7, 6, 12]
answer = [7, 6, -1, -1]        // nothing to the right of 6 is smaller

Example 3

arr    = [2, 2, 2]
answer = [-1, -1, -1]          // equal is not smaller

Approach 1: Brute force

Intuition. Follow the definition: from every index, walk right until a smaller value shows up. Each walk is independent, so the same elements get re-read over and over, and an increasing array (where every answer is -1) makes every walk run to the end.

Algorithm.

  1. For each i, set res[i] = -1.
  2. Scan j = i + 1, i + 2, ...; at the first arr[j] < arr[i], record arr[j] and stop.
  3. Return res.
static int[] bruteForce(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    for (int i = 0; i < n; i++) {
        res[i] = -1;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[i]) {
                res[i] = arr[j];
                break;
            }
        }
    }
    return res;
}

Complexity. Time O(n^2) in the worst case, for example on [1, 2, 3, ..., n]. Space O(1) besides the output.

Approach 2: Optimal, monotonic increasing stack

Intuition. Scan from right to left and keep a stack of elements to the right that might still be the answer for something further left. The deciding observation:

When we reach arr[i], any candidate x ≥ arr[i] sitting to its right is useless from now on.

Take any index j < i. If x < arr[j], then arr[i] ≤ x < arr[j], so arr[i] is also smaller than arr[j] and it is closer. The scan from j would stop at arr[i] (or earlier) and never reach x. So we pop every candidate that is ≥ arr[i].

What remains on top is the nearest element to the right that is strictly smaller than arr[i], which is the answer. Then push arr[i], the newest and closest candidate for the indices to its left.

The stack is monotonic: from bottom to top its values strictly increase, so reading from the top downwards they strictly decrease while their positions move further right. This is the mirror image of the next greater element stack, and the only code difference is the direction of the comparison.

Algorithm.

  1. Create an empty stack.
  2. For i from n - 1 down to 0:
    • Pop while the top is ≥ arr[i].
    • res[i] is the top, or -1 if the stack is empty.
    • Push arr[i].
  3. Return res.
static int[] optimal(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = n - 1; i >= 0; i--) {
        while (!st.isEmpty() && st.peek() >= arr[i]) st.pop();   // arr[i] is nearer and no larger: they can never win again
        res[i] = st.isEmpty() ? -1 : st.peek();
        st.push(arr[i]);
    }
    return res;
}

Dry run on [4, 8, 5, 2, 25] (stack shown top first):

i arr[i] popped res[i] stack after push
4 25 none -1 25
3 2 25 -1 2
2 5 none 2 5, 2
1 8 none 5 8, 5, 2
0 4 8, 5 2 4, 2

Result [2, 5, 2, -1, -1].

Complexity. Time O(n): each element is pushed once and popped at most once, so the inner while loop runs at most n times across the entire scan, even though a single step can pop several values. Space O(n) for the stack, which holds everything on a decreasing array such as [3, 2, 1].

Variant: nearest smaller element on the left

Scanning left to right with exactly the same pop rule gives the nearest strictly smaller element on the left (the “previous smaller element”). The argument is symmetric: once arr[i] has been seen, any earlier value ≥ arr[i] can never be the nearest smaller element for anything to the right of i.

static int[] previousSmaller(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> st = new ArrayDeque<>();
    for (int i = 0; i < n; i++) {
        while (!st.isEmpty() && st.peek() >= arr[i]) st.pop();
        res[i] = st.isEmpty() ? -1 : st.peek();
        st.push(arr[i]);
    }
    return res;
}

For [4, 5, 2, 10, 8] this returns [-1, 4, -1, 2, 2].

All four “nearest” questions share one template; only the scan direction and the pop condition change:

want scan pop while the top is
next greater (right side) right to left <= arr[i]
next smaller (right side) right to left >= arr[i]
previous greater (left side) left to right <= arr[i]
previous smaller (left side) left to right >= arr[i]

Pushing indices instead of values is a small change that unlocks many harder problems, because the distance to the nearest smaller element tells you how far a value can stretch as a minimum. That is the engine behind the histogram and subarray-minimum problems linked below.

Edge cases and pitfalls