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]