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.
- Difficulty: Easy
- Topics: Arrays, Stack, Monotonic Stack
- Asked at: Amazon, Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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^50 <= arr[i] <= 10^9
Hints for Nearest Smaller Element
Hint 1
Scanning left from every position is O(n²) on a sorted array. Which earlier values can never be an answer again?
Hint 2
Once a value
vappears, every earlier value>= vis hidden behind it for all later positions.Hint 3
Keep a stack of values increasing from bottom to top: pop values
>= arr[i], the top (if any) is the answer, then pusharr[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
- Keep a stack of values, strictly increasing from bottom to top.
- For each
arr[i], pop while the top is>= arr[i]. - The answer is the top if the stack is non-empty, otherwise
-1. - 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 resJava
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