Problem Statement
Given an array, find the first smaller element on the right for every element.
If no such element exists, return -1.
Brute Force Intuition
For every element:
Scan towards the right.
The first smaller element is the answer.
Complexity
- Time Complexity: O(N²)
- Space Complexity: O(1)
Brute Force Code
class Solution {
public int[] nextSmaller(int[] arr) {
int n = arr.length;
int[] ans = new int[n];
for (int i = 0; i < n; i++) {
ans[i] = -1;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[i]) {
ans[i] = arr[j];
break;
}
}
}
return ans;
}
}
Moving Towards the Optimal Approach
Instead of searching to the right every time:
Traverse from:
Right → Left
Maintain a stack containing only useful candidates.
Pattern Recognition
Whenever you see:
- Next Smaller
- Previous Smaller
- Next Greater
- Previous Greater
Think:
Monotonic Stack
Optimal Approach
For every element:
Remove all elements:
>= Current Element
If stack is empty:
Answer = -1
Else:
Answer = Stack Top
Push current element.
Optimal Java Solution
class Solution {
public int[] nextSmaller(int[] arr) {
int n = arr.length;
int[] ans = new int[n];
Stack<Integer> st = new Stack<>();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() &&
st.peek() >= arr[i]) {
st.pop();
}
ans[i] = st.isEmpty()
? -1
: st.peek();
st.push(arr[i]);
}
return ans;
}
}
Dry Run
arr = [4,8,5,2,25]
Process from right:
25 → -1
2 → -1
5 → 2
8 → 5
4 → 2
Answer:
[2,5,2,-1,-1]
Complexity Analysis
| Metric | Complexity |
|---|---|
| Time | O(N) |
| Space | O(N) |
Interview One-Liner
Traverse from right using a monotonic increasing stack so the top always represents the next smaller element.