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

ANSV

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: Hrishikesh Mishra