Next Smaller Element to the Right
Implement nextSmallerElement
Given an integer array
arr, 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.
Example 1:
Input: arr = [8,4,2,9,3,7,1]
Output: [4,2,1,3,1,1,-1]
Example 2:
Input: arr = [1,2,3,4,5]
Output: [-1,-1,-1,-1,-1]
Example 3:
Input: arr = [5,4,3,2,1]
Output: [4,3,2,1,-1]
+ 4 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ arr.length ≤ 15 - ●
0 ≤ arr[i] ≤ 1000
arr =
[8, 4, 2, 9, 3, 7, 1]