Next Smaller Element to the Right
Solve this Problemarr, find, for every position, the value of the nearest element strictly smaller than it to its right — or -1 if no such element exists.
This is the mirror image of finding the nearest smaller element to the left: the same monotonic-stack idea applies, just scanning from the end of the array backward instead of from the start forward. A stack kept in increasing order from bottom to top, with anything greater-or-equal popped off before each new value is pushed, gives every position its answer in O(1) amortized work — a smaller value discovered closer to a position permanently rules out any larger value farther away from ever being the answer, regardless of which direction the scan runs.
Test Case 1:
Test Case 2:
Test Case 3:
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 Forward for Each Position
BruteFor every position i, scan forward from i+1 toward the end, looking for the first value smaller than arr[i]. The first one found is the answer; if the scan reaches the end without finding one, the answer is -1. Correct, but each position can trigger a scan through nearly the whole rest of the array — O(n) per position, O(n²) overall.
O(n²)O(n)1class Solution {
2 public int[] nextSmallerElement(int[] arr) {
3 int n = arr.length;
4 int[] result = new int[n];
5 for (int i = 0; i < n; i++) {
6 result[i] = -1;
7 for (int j = i + 1; j < n; j++) {
8 if (arr[j] < arr[i]) {
9 result[i] = arr[j];
10 break;
11 }
12 }
13 }
14 return result;
15 }
16}Optimal — Monotonic Increasing Stack, Scanning Right to Left
OptimalWalk the array from the end backward, keeping a stack that only ever holds values in increasing order from bottom to top — exactly the same trick as finding the nearest smaller element to the left, just scanning in the opposite direction. Before recording an answer for position i, pop off anything on top of the stack that's greater than or equal to arr[i], since those values can never be the nearest-smaller-to-the-right for i or for anything further left. What's left on top (if anything) is the answer. Every value is pushed once and popped at most once — O(n) total.
O(n)O(n)1class Solution {
2 public int[] nextSmallerElement(int[] arr) {
3 int n = arr.length;
4 int[] result = new int[n];
5 Deque<Integer> stack = new ArrayDeque<>();
6 for (int i = n - 1; i >= 0; i--) {
7 while (!stack.isEmpty() && stack.peek() >= arr[i]) {
8 stack.pop();
9 }
10 result[i] = stack.isEmpty() ? -1 : stack.peek();
11 stack.push(arr[i]);
12 }
13 return result;
14 }
15}