All nearest smaller values

In computer science, the all nearest smaller values (ANSV) problem is: given an array ${\displaystyle A[1..n]}$, compute for each position the index ${\displaystyle P[i]=\max\{\,j<i\mid A[j]<A[i]\,\}}$, using a sentinel value (e.g. ${\displaystyle 0}$) when no such ${\displaystyle j}$ exists. The corresponding nearest-smaller value is ${\displaystyle A[P[i]]}$. Some presentations report ${\displaystyle A[P[i]]}$, but many applications require the indices ${\displaystyle P[i]}$.

This problem can be solved efficiently both by parallel and non-parallel algorithms: Berkman, Schieber & Vishkin (1993), who first identified the procedure as a useful subroutine for other parallel programs, developed efficient algorithms to solve it in the Parallel Random Access Machine model; it may also be solved in linear time on a non-parallel computer using a stack-based algorithm. Later researchers have studied algorithms to solve it in other models of parallel computation.