Nearest Smaller Element

Easy
1416.

Nearest Smaller Element

Nearest Smaller Element is an easy coding problem on arrays, stack and monotonic stack, asked in Amazon, Microsoft and Flipkart interviews.

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
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @return {number[]}
 */
var prevSmaller = function(arr) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Nearest Smaller Element — Solution in Python, Java & C++

Nearest Smaller Element solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Nearest Smaller Element is an easy coding problem on arrays, stack and monotonic stack, asked in Amazon, Microsoft and Flipkart interviews.

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

Hints for Nearest Smaller Element

  1. Hint 1

    Scanning left from every position is O(n²) on a sorted array. Which earlier values can never be an answer again?

  2. Hint 2

    Once a value v appears, every earlier value >= v is hidden behind it for all later positions.

  3. Hint 3

    Keep a stack of values increasing from bottom to top: pop values >= arr[i], the top (if any) is the answer, then push arr[i].

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

Java

public static int[] prevSmaller(int[] arr) {
    int n = arr.length;
    int[] res = new int[n], st = new int[n];
    int top = 0;
    for (int i = 0; i < n; i++) {
        while (top > 0 && st[top - 1] >= arr[i]) top--;
        res[i] = top > 0 ? st[top - 1] : -1;
        st[top++] = arr[i];
    }
    return res;
}

C++

vector<int> prevSmaller(vector<int>& arr) {
    vector<int> st, res;
    for (int x : arr) {
        while (!st.empty() && st.back() >= x) st.pop_back();
        res.push_back(st.empty() ? -1 : st.back());
        st.push_back(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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Stack Data Structure