Find the Next Smaller Element in an Array

Title: Find the Next Smaller Element in an Array

The next smaller element problem is the mirror image of the classic next greater element question, and it shows up just as often in interviews. In this guide, we will explore how to find, for every element in an array, the first element to its right that is strictly smaller than it. You will learn a clean O(n) approach using a stack, see a complete Java program, walk through a step-by-step trace, and practice the interview follow-ups that usually come after the base solution.

Understanding the Problem

Given an integer array nums, we want to produce a result array of the same length where result[i] holds the first element to the right of index i that is strictly smaller than nums[i]. If no such element exists, result[i] should be -1.

For example, for the input {4, 8, 5, 2, 25}, the next smaller element of 4 is 2, the next smaller element of 8 is 5, and the next smaller element of 25 does not exist because nothing to its right is smaller, so it becomes -1.

A brute-force solution checks, for every index, every element to its right until it finds a smaller one. That works but costs O(n squared) in the worst case, such as a strictly increasing array. A stack lets us answer every index in a single linear pass.

Approach to Find the Next Smaller Element

The key idea is to scan the array from right to left while keeping a stack of ‘candidate’ values, that is, values that could still be the next smaller element for something further to the left. Here are the steps:

1. Create a result array of the same length as nums and an empty stack.
2. Iterate i from the last index down to 0.
3. While the stack is not empty and its top is greater than or equal to nums[i], pop it; those values can never be the answer for nums[i] or for anything to the left of it.
4. After the popping stops, the stack is either empty, meaning no smaller element survives, or its top is the next smaller element for nums[i].
5. Set result[i] to -1 if the stack is empty, otherwise to the stack’s top value.
6. Push nums[i] onto the stack so it becomes a candidate answer for elements further to the left.
7. After the loop finishes, result holds the next smaller element for every index.

Java Program to Find the Next Smaller Element

Let us put the approach into a full, compilable Java program:

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class NextSmallerElement {

    public static int[] nextSmallerElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= nums[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(nums[i]);
        }

        return result;
    }

    public static void main(String[] args) {
        int[] nums = {4, 8, 5, 2, 25};
        int[] result = nextSmallerElements(nums);

        System.out.println("Array: " + Arrays.toString(nums));
        System.out.println("Next Smaller Elements: " + Arrays.toString(result));
    }
}

Explanation of the Program

• The method nextSmallerElements takes the array nums and returns a new array of the same size.
• A Deque<Integer> is used as the stack because the standard Stack class is older and ArrayDeque is the recommended stack implementation in modern Java.
• The loop walks the array from the last index to the first so that, at the moment we process nums[i], the stack already contains the useful candidates from everything to the right of i.
• The inner while loop discards stack values that are not strictly smaller than nums[i], since a larger or equal value can never be the next smaller element for nums[i].
• After the inner loop, whatever remains on top of the stack, if anything, is the first value to the right of i that is strictly smaller than nums[i].
• nums[i] is pushed last so it is available as a candidate for the next index processed, which is i - 1.

Step-by-Step Trace

Let us trace the algorithm on the input {3, 7, 1, 4, 2}, scanning from index 4 down to index 0.

At the end of each iteration, the stack holds an increasing sequence of values that are still candidates for elements further to the left, and result[i] already holds the correct next smaller element for index i.

Examples

Let us look at a few concrete runs to see how the stack behaves on different shapes of input.

Example 1: A Typical Mixed Array

int[] nums1 = {4, 10, 5, 8, 2};
System.out.println(Arrays.toString(nextSmallerElements(nums1)));
// Output: [2, 5, 2, 2, -1]

Every value except 2 finds a smaller value somewhere to its right. 2 is the smallest value in the array and has nothing smaller after it.

Example 2: A Strictly Increasing Array

int[] nums2 = {2, 5, 9, 13};
System.out.println(Arrays.toString(nextSmallerElements(nums2)));
// Output: [-1, -1, -1, -1]

When the array is strictly increasing, every element is the smallest value from its position to the end, so every entry in result is -1.

Example 3: A Strictly Decreasing Array

int[] nums3 = {9, 7, 5, 3, 1};
System.out.println(Arrays.toString(nextSmallerElements(nums3)));
// Output: [7, 5, 3, 1, -1]

In a strictly decreasing array, the very next element is always smaller than the current one, so result[i] equals nums[i + 1] for every index except the last, which has nothing after it.

Common Mistakes to Avoid

Here are the slip-ups learners tend to make when implementing the stack-based next smaller element solution:

• Defaulting to 0 instead of -1 – Java’s int[] initializes every slot to 0, so an element with no smaller value to its right silently reports 0, which looks like a real answer instead of ‘none found’. Explicitly assign -1 when the stack is empty.
• Popping only on strict greater-than – for arrays with duplicate values like {3, 7, 1, 4, 2} extended to include a repeated value, using > instead of >= leaves an equal value on the stack, which then gets returned as the ‘next smaller’ element even though it is only equal. Pop while stack.peek() >= nums[i].
• Forgetting to push nums[i] after computing result[i] – the current element is a valid candidate answer for everything still to its left, so skipping the push makes earlier indices compute their result against a stale, larger stack. Always push right after assigning the result.
• Mixing left-to-right and right-to-left logic – the right-to-left version looks up the answer before pushing, while a left-to-right version resolves answers for earlier indices when a smaller value finally arrives. Combining the two styles produces a result array filled with elements that came before the current index instead of after it.
• Storing indices but printing them as if they were values – if the stack holds indices instead of raw numbers, printing stack.peek() directly gives a position in the array, not the next smaller number. Decide upfront whether the stack holds values or indices and stay consistent.

Edge Cases to Test

Before you declare the implementation done, run the algorithm against these boundary inputs:

• Empty array
• Single-element array
• Strictly increasing array (every result is -1)
• Strictly decreasing array (every result is the next element)
• All elements identical
• Minimum value at the last index
• Integer.MIN_VALUE present
• Null array reference

Additional Considerations

A few points worth remembering about this algorithm:

1. Time complexity: Although there is a nested while loop, every value is pushed onto the stack exactly once and popped at most once across the entire run, so the total work is O(n), not O(n squared).
2. Space complexity: The result array is O(n), and the stack can hold up to n elements in the worst case, such as a strictly increasing input where nothing ever gets popped. Overall extra space is O(n).
3. Why Integer.MIN_VALUE matters: An element equal to Integer.MIN_VALUE can never have a next smaller element, so it is a useful stress value for confirming your -1 handling is correct.
4. Direction of traversal: Scanning right to left lets you look up the answer immediately because the stack always holds valid candidates for the current index. A left-to-right scan is also O(n) but needs to resolve earlier indices retroactively, which is harder to reason about.

Interview Follow-up Questions

Once the base version is working, an interviewer will usually probe deeper with questions like these:

• What if the array is circular, so the next smaller element can wrap around to the front? – iterate the index range twice, from 0 to 2n - 1, using i % n to let elements near the end see candidates near the start, without physically duplicating the array.
• What if you need the previous smaller element to the left instead of the next one to the right? – keep the same stack-based idea but scan left to right, pushing and resolving against values already seen; the complexity stays O(n).
• What if you are given nums1 and nums2, where nums1 is a subset of nums2, and need the next smaller element for each nums1 entry within nums2? – compute the next-smaller map for all of nums2 once using this stack approach, then answer each nums1 query with an O(1) lookup, for O(n + m) overall.
• What if the array is a stream of unknown length and you cannot rewind? – buffer unresolved elements on the stack as before, but accept that any element still on the stack when the stream ends has no next smaller element; resolve entries only as smaller values arrive.
• What if the array has billions of elements and must stay within a fixed memory budget? – note that the stack can hold the entire array in the worst case, such as a strictly increasing input, so an exact streaming solution still needs O(n) auxiliary space; only an approximate or windowed answer can run in bounded memory.

Conclusion

In this guide, we solved the next smaller element problem in Java using a single stack and a right-to-left scan, bringing the running time down from O(n squared) to O(n). You now have a complete program, a worked trace, concrete examples, and a checklist of common mistakes and interview follow-ups to lean on.

Try adapting the code to a circular array, to the previous smaller element variant, or to the two-array lookup version to see how the same stack idea solves a whole family of problems. Happy coding!

You can learn more about Array techniques: Arrays