Next Smaller Element

ArrayMonotonic StackStack

Given an array of integers, for each element, find the first next element that is smaller than the current element and output their indexes. If no smaller element is found to the right for a number, output -1 for that number. The output should be an array of integers representing the indexes of the next smaller elements.

Example 1

Input

[
  2,
  1,
  4,
  3
]

Output

[1, -1, 3, -1]

Explanation. For `2`, the next smaller is `1` at index 1. `1` doesn't have a next smaller so `-1`, for `4` the next smaller is `3` at index 3. `3` doesn't have a next smaller so `-1`.

Example 2

Input

[
  3,
  8,
  4,
  5,
  2
]

Output

[4, 2, 4, 4, -1]

Explanation. Indexes are calculated based on the first next smaller element. There is no smaller element after `2`, hence `-1`.

Example 3

Input

[
  7,
  7,
  7,
  7
]

Output

[-1, -1, -1, -1]

Explanation. No element is smaller to the right of any `7`.

Example 4

Input

[
  5
]

Output

[-1]

Explanation. Only one element, so no next element to compare.

Follow-up: Can you solve it in O(n) time using a stack?

Constraints:

The length of the input array can be up to 10,000. All the elements in the array will be integers and range between -10,000 to 10,000.

Views: 4