Previous Smaller Element for Each Array Position

Medium20–25 min

Topics

StackArrayMonotonic Stack

Companies

AmazonMicrosoftGoogle

Given an integer array arr, find, for every position, the value of the nearest element strictly smaller than it to its left — or -1 if no such element exists. Scanning backward from every position independently works but repeats a lot of comparisons that a smarter approach can skip entirely. The key insight: once a smaller value appears, every larger value sitting behind it becomes permanently irrelevant — no future position will ever "see past" the smaller, closer value to reach them. A monotonic stack exploits exactly that: keep only values in increasing order, discarding anything that a smaller arrival has made obsolete, and whatever survives on top at each step is precisely the answer.

Test Case 1:

Input:arr = [7, 3, 9, 2, 6, 1, 8]

Output:[-1, -1, 3, -1, 2, -1, 1]

Explanation:For each position, the nearest strictly smaller value found scanning left: 7 has none, 3 has none, 9's nearest smaller-to-the-left is 3, 2 has none, 6's is 2, 1 has none, 8's is 1.

Test Case 2:

Input:arr = [5, 4, 3, 2, 1]

Output:[-1, -1, -1, -1, -1]

Explanation:Strictly decreasing — every element is smaller than everything before it, so nothing to its left is ever smaller than it.

Test Case 3:

Input:arr = [1, 2, 3, 4, 5]

Output:[-1, 1, 2, 3, 4]

Explanation:Strictly increasing — every element's immediate left neighbor is always its answer.

Constraints

◆1 ≤ arr.length ≤ 15
◆0 ≤ arr[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Scan Backward for Each Position

Brute

For every position i, scan backward from i-1 toward the start, looking for the first value smaller than arr[i]. The first one found (closest to i) is the answer; if the scan reaches the beginning without finding one, the answer is -1. Correct, but each position can trigger a scan through nearly the whole array before it — O(n) per position, O(n²) overall.

TimeO(n²)

SpaceO(n)

Java

Try it out

class Solution {
    public int[] previousSmallerElement(int[] arr) {
        int n = arr.length;
        int[] result = new int[n];
        for (int i = 0; i < n; i++) {
            result[i] = -1;
            for (int j = i - 1; j >= 0; j--) {
                if (arr[j] < arr[i]) {
                    result[i] = arr[j];
                    break;
                }
            }
        }
        return result;
    }
}

Optimal — Monotonic Increasing Stack

Optimal

Keep a stack that only ever holds values in increasing order from bottom to top. For each new element, first pop off anything on top that's greater than or equal to it — those values can never be the answer for this or any later element, since the current element is smaller and closer. Whatever's left on top after popping (if anything) is exactly the nearest smaller element to the left. Push the current value and move on. Every value is pushed once and popped at most once, so the total work across the whole array is O(n).

TimeO(n)