# All nearest smaller values (ANSV)

### 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])`

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

```
Author: