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