Find the Previous Smaller Element in an Array

Title: Find the Previous Smaller Element in an Array

In this guide, you will learn how to find the previous smaller element for every entry in an array of integers. This is a classic array and stack problem that shows up often in coding interviews, and it is a great way to practice recognizing when a monotonic stack beats a brute force nested loop.

By the end of this article you will understand the problem statement, walk through an efficient stack based approach, trace the algorithm by hand, and see worked examples. We will also cover common mistakes, edge cases, and a few interview follow up questions so you are ready to discuss this problem confidently.

Understanding the Problem

Given an array of integers numbers, you need to find, for every index i, the nearest element to the left of numbers[i] that is strictly smaller than numbers[i]. If no such element exists, the answer for that index is -1.

For example, given the array [4, 8, 5, 2, 25], the previous smaller element of 8 is 4 because 4 is the closest element to its left that is smaller than 8. The previous smaller element of 2 is -1 because every element to its left, 4, 8, and 5, is greater than or equal to 2.

The naive approach checks every earlier index for each element, which costs O(n^2) time. The goal is to solve it in O(n) time using a stack that only ever holds candidates that could still be a previous smaller element for some future index.

Approach / Algorithm Steps

1. Create an empty Stack<Integer> to hold candidate values, and a result array of the same length as numbers.
2. Iterate over numbers from left to right using index i.
3. While the stack is not empty and the element at the top of the stack is greater than or equal to numbers[i], pop the stack. These popped elements can never be the previous smaller element for numbers[i] or for anything after it, because numbers[i] is both closer and smaller.
4. After the while loop, if the stack is empty, there is no previous smaller element, so set result[i] to -1. Otherwise set result[i] to the value at the top of the stack.
5. Push numbers[i] onto the stack so it becomes a candidate for later indices.
6. Repeat steps 3 to 5 for every index until the array is exhausted, then return result.

Java Program

The following program implements the stack based approach described above.

import java.util.Arrays;
import java.util.Stack;

public class PreviousSmallerElement {

    public static int[] findPreviousSmallerElements(int[] numbers) {
        int n = numbers.length;
        int[] result = new int[n];
        Stack<Integer> stack = new Stack<>();

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

    public static void main(String[] args) {
        int[] numbers = {4, 8, 5, 2, 25};
        int[] result = findPreviousSmallerElements(numbers);
        System.out.println("Input array: " + Arrays.toString(numbers));
        System.out.println("Previous smaller elements: " + Arrays.toString(result));
    }
}

Explanation of the Program

• findPreviousSmallerElements allocates a result array the same size as numbers and an empty Stack<Integer> called stack.
• The while loop pops any value from stack that is greater than or equal to numbers[i], because those values are no longer useful candidates once a smaller element has appeared.
• After the while loop, stack.isEmpty() tells us whether any valid candidate survived. An empty stack means result[i] is -1; otherwise stack.peek() is the previous smaller element.
• stack.push(numbers[i]) adds the current value as a candidate for later indices, which keeps the stack sorted in strictly increasing order from bottom to top.
• The main method runs the function on a sample array and prints both the input and the resulting array using Arrays.toString.

Step-by-Step Trace

Let’s trace the algorithm on the array [5, 1, 4, 2, 8, 3] and watch how the stack changes on every iteration.

At the end of each iteration, stack holds a strictly increasing sequence of values from bottom to top, and result[i] holds the nearest strictly smaller element to the left of numbers[i], or -1 if none exists.

Examples

Example 1: Basic Array

Given the array [4, 8, 5, 2, 25], each element’s previous smaller value is computed as follows.

int[] numbers = {4, 8, 5, 2, 25};
int[] result = findPreviousSmallerElements(numbers);
// Output: [-1, 4, 4, -1, 2]

Example 2: Array with Duplicate Elements

When every element has the same value, no element is ever strictly smaller than an earlier one, so every result is -1.

int[] numbers = {3, 3, 3};
int[] result = findPreviousSmallerElements(numbers);
// Output: [-1, -1, -1]

Example 3: Mixed Decreasing then Increasing Values

This array starts by decreasing and then increases, so the first three elements have no previous smaller element while the later elements find one quickly.

int[] numbers = {10, 4, 3, 5, 6, 7};
int[] result = findPreviousSmallerElements(numbers);
// Output: [-1, -1, -1, 3, 5, 6]

Common Mistakes to Avoid

These are the mistakes that most often trip up candidates solving this exact problem.

• Forgetting to push the current element. The stack never grows past its first pop, so every result after the first index stays -1 even though smaller elements clearly exist. Always call stack.push(numbers[i]) after computing result[i].
• Using > instead of >= in the while condition. Duplicate values are kept on the stack and incorrectly reported as the previous smaller element for later ties, so {3, 3, 3} would wrongly return [-1, 3, 3]. Pop while stack.peek() >= numbers[i] so equal values are treated as not smaller.
• Calling peek() without checking isEmpty() first. On a strictly decreasing array like {9, 7, 5}, every element pops the stack empty, and an unchecked peek() throws EmptyStackException. Always test stack.isEmpty() before reading peek().
• Confusing previous smaller with next smaller. Iterating from the right instead of the left produces the mirrored answer for the next smaller element, not the previous one. Keep the loop direction left to right for this problem.
• Reusing a single static stack across calls. Leftover values from a prior call stay on the stack and corrupt the first few results of the next array. Create a fresh Stack<Integer> inside the method, or clear it explicitly before reuse.

Edge Cases to Test

Walk through these inputs out loud before you are asked to; interviewers notice candidates who raise edge cases unprompted.

• Empty array
• Single-element array
• Strictly increasing elements
• Strictly decreasing elements
• All identical elements
• Negative numbers present
• Integer.MIN_VALUE present

Additional Considerations

The stack based approach runs in O(n) time. Although the while loop can run multiple times per index, each element is pushed exactly once and popped at most once across the entire run, so the total number of push and pop operations is bounded by 2n.

Space complexity is O(n) for the stack in the worst case, for example when numbers is already strictly increasing and nothing is ever popped, plus O(n) for the result array.

Compared with the brute force nested loop, which is O(n^2) time and O(1) extra space, the stack approach trades a small amount of memory for a large improvement in running time on large inputs.

Integer.MIN_VALUE is worth testing because it can never have a previous smaller element. Make sure your comparison logic does not accidentally treat it as equal to some sentinel value you might otherwise use instead of -1.

Interview Follow-up Questions

Once you have the base solution working, expect an interviewer to push further with questions like these.

• What if you need the next smaller element instead? Run the same stack logic from right to left, still popping while the stack top is greater than or equal to the current value.
• What if duplicates should also count as smaller? Change the popping condition from >= to > so equal values remain valid candidates.
• What if the array arrives as a stream of unknown length? The algorithm is already online since it only looks left, so you can keep the same stack alive and process each new value as it arrives.
• What if you must solve it using O(1) extra space beyond the output? This is generally not possible for an arbitrary array without sacrificing O(n) time; discuss the space-time trade-off and when a brute force O(n^2) solution might be acceptable instead.
• What if the array is too large to fit in memory? Partition the array into chunks, compute previous smaller elements independently within each chunk, then do a second pass to patch any result at a chunk boundary using the minimum of all prior chunks.

Conclusion

Finding the previous smaller element for every position in an array is a great example of how a monotonic stack turns an O(n^2) brute force idea into an O(n) solution. Once you recognize the pattern, the same stack trick solves the next smaller, next greater, and previous greater element problems with only small tweaks.

Try adapting the program above to return indices instead of values, or to solve the next greater element variant, to make sure the pattern has really sunk in. You can learn more about array based problems like this one on the Arrays category page.