### All nearest smaller values (ANSV)

##### The all nearest smaller values problem is the following task: for each position in a sequence of numbers, search among the previous positions for the last position that contains a smaller value.

Example:

Input = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15}.

Output = {—, 0, 0, 4, 0, 2, 2, 6, 0, 1, 1, 5, 1, 3, 3, 7}

##### Algorithm:

- We need stack to hold all smaller that found till particular position in array
- Now take an stack and push 0
- Take array S for nearest smaller values and put S[0] = -∞
- Iterate input array from index 1 to n-1
- If
`stack.top > array[i]`

then,`stack.pop`

- Repeat this process till stack is not empty or above condition doesn’t break
- At this point, we have two cases
- Case 1: When stack is empty – means no smaller value than current one
- Case 2: When stack is not empty – means top of stack has nearest smaller values for this element

- If stack is empty then
`S[i] = -∞`

- Else
`S[i] = stack.top`

`stack.push(array[i])`

- If

Latest Source Code:

Github: AllNearestSmallerValue.java

**Output:**

Input ANSV 0 - 8 0 4 0 12 4 2 0 10 2 6 2 14 6 1 0 9 1 5 1 13 5 3 1 11 3 7 3 15 7