Nearest Smaller Element — Easy Problem & Solution

Problem statement

For every position i of the array arr, find the nearest smaller element to its left: the value arr[j] with the largest index j < i such that arr[j] < arr[i] (strictly smaller).

If no element to the left of i is smaller, the answer for i is -1. Return the array of answers.

Example 1

Input: arr = [4,5,2,10,8]
Output: [-1,4,-1,2,2]
Explanation: For 8 the nearest smaller value to the left is 2 — 10 is larger.

Example 2

Input: arr = [6,2,7,7,3,9]
Output: [-1,-1,2,2,2,3]
Explanation: The second 7 skips the first: equal is not smaller.

Example 3

Input: arr = [3,2,1]
Output: [-1,-1,-1]

Constraints

• 1 <= arr.length <= 10^5
• 0 <= arr[i] <= 10^9

How to solve Nearest Smaller Element

The candidates for 'nearest smaller to the left' form an increasing sequence, so a monotonic stack holds exactly them.

Approach

1. Keep a stack of values, strictly increasing from bottom to top.
2. For each arr[i], pop while the top is >= arr[i].
3. The answer is the top if the stack is non-empty, otherwise -1.
4. Push arr[i].

Why it works

A popped value v >= arr[i] lies to the left of i, so for any later position the element arr[i] is both nearer and no larger — v could only be the answer if arr[i] also were, and arr[i] would win by being nearer. What remains on the stack after popping are values smaller than arr[i], and the top is the nearest of them.

Complexity

• Time — O(n) — each value is pushed and popped at most once
• Space — O(n)

Pitfalls

• Pop on >=, not >: an equal value is not smaller.
• The answer is the value, not the index.
• Push the current value after answering, not before.

Reference solution

Python

from typing import List

def prevSmaller(arr: List[int]) -> List[int]:
    st = []
    res = []
    for x in arr:
        while st and st[-1] >= x:
            st.pop()
        res.append(st[-1] if st else -1)
        st.append(x)
    return res

JavaScript

var prevSmaller = function(arr) {
    var st = [], res = [];
    for (var i = 0; i < arr.length; i++) {
        while (st.length > 0 && st[st.length - 1] >= arr[i]) st.pop();
        res.push(st.length > 0 ? st[st.length - 1] : -1);
        st.push(arr[i]);
    }
    return res;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Available Captures for Rook Easy
• Delete Columns to Make Sorted Easy
• Maximize Sum Of Array After K Negations Easy
• Minimum Positive Sum Subarray Easy
• Find X-Sum of All K-Long Subarrays I Easy
• Valid Boomerang Easy