Is sorting the data first a solution?

Not for the original problem. Sorting changes the positional relationships that the answer is meant to describe.

Can the values be nonnumeric?

Yes, if they have a consistent total ordering suitable for the task. The algorithm relies on comparisons rather than arithmetic distance.

Must both directions be computed?

No. Some applications need only previous or next smaller values. The full problem commonly asks for both.

AI Glossary / Data engineering and architecture / Intermediate

All nearest smaller values

Definition

The all nearest smaller values problem finds, for every element in an ordered sequence, the closest earlier and closest later elements that are strictly smaller. Closeness refers to position in the sequence, not numerical similarity.

What it means

For a sequence of measurements, the question is not “Which value is smallest overall?” It is “Looking left or right from this position, which smaller value do I encounter first?” Some positions have no qualifying neighbor on one or both sides.

The usual output stores the neighbors' indices, which retain their positions and allow later calculations. Reporting only values can be ambiguous when the sequence contains repetitions. A left-only version asks for previous smaller elements; a right-only version asks for next smaller elements.

This is a deterministic array-processing problem, not a nearest-neighbor machine-learning method. It is useful as a building block in other algorithms, including structures for range-minimum queries. It avoids repeated searches through overlapping sequence portions.

How it works

A simple sequential method scans left to right while maintaining a stack of candidate indices. Before processing a new value, it removes candidates whose values are greater than or equal to that value. The surviving top, if any, is the nearest strictly smaller value to the left. It records that index and pushes the new index.

Removing a candidate is safe for this left-match computation: the new value is at least as useful for future positions because it is no larger and closer to them. The stack's retained values are strictly increasing from bottom to top.

Each index is pushed once and popped at most once, so the total work is linear in the sequence length, even though one particular step may pop many elements. Scanning in the reverse direction finds right matches with the same principle.

Parallel methods use additional decomposition and combination techniques. Their performance claims depend on the computational model and implementation.

Three practical examples

A monitoring tool computes how many recorded observations back the most recent lower measurement occurred, under a clearly stated comparison rule.
An algorithm library uses nearest-smaller relationships while building a Cartesian-tree representation of a sequence.
A developer compares a linear stack implementation with a repeated-search reference implementation on increasing, decreasing and repeated-value inputs.

Think of it this way

Think of standing in a line of people and looking along the line for the first person shorter than you. The relevant person is the nearest qualifying position, not the person whose height is numerically closest to yours.

The analogy only explains ordering. An array can contain arbitrary comparable values, and software can inspect indices in either direction. It also makes the tie rule visible: someone of exactly equal height does not qualify when the condition is strictly shorter.

Worked example

Finding both neighbors

Use the sequence [6, 2, 5, 5, 1, 4], with positions numbered 1 through 6. Its nearest-smaller indices on the left are [none, none, 2, 2, none, 5]. Its nearest-smaller indices on the right are [2, 5, 5, 5, none, none].

For position 4, the value is 5. Position 3 also contains 5, so it does not qualify as strictly smaller. Continuing left reaches value 2 at position 2. Looking right immediately reaches value 1 at position 5.

For position 1, value 2 at position 2 is the nearest smaller value on the right, even though the later value 4 is numerically closer to 6. Positional distance determines the answer.

During a left-to-right stack scan, the second 5 removes the earlier 5 as a candidate before recording position 2 as its left match. When the value 1 arrives, it removes all remaining candidates and has no left match. Each removal happens only once, which explains the linear total work rather than a separate full search for every position.

Illustrative case study

A fictional operations team builds a chart showing how far back the latest strictly lower queue measurement occurred. Its first implementation treats equal measurements as lower, producing misleading markers on long flat sections.

The team writes down the comparison rule and checks a small sequence by hand. It corrects the stack's removal condition and stores indices so that repeated values remain distinguishable. It also distinguishes distance in recorded observations from elapsed clock time when samples are irregularly spaced.

The result is an accurately defined descriptive feature. The team does not interpret the feature alone as evidence of a trend or a forecast. The case is fictional.

Common misconceptions and mistakes

Nearest means closest in sequence position, not closest numerical value.
Strictly smaller excludes equal values; a smaller-or-equal variant needs different handling.
A missing match is a valid result, not necessarily an error.
Linear total work does not mean every individual scan step takes constant time.
Index distance is not elapsed time unless the sampling schedule supports that interpretation.

Business use

This problem supports efficient features and analytical structures over long ordered datasets.

Before adopting such a feature, define the sequence order, comparison relation and missing-result representation. For historical prediction, using a right-hand match may incorporate future observations and create data leakage; a left-only computation may be appropriate instead. Test repeated values and boundary positions explicitly. A fast implementation of the wrong directional or tie convention is still the wrong analysis.

Check your understanding

In [3, 7, 6], what is the nearest strictly smaller value to the left of the final 6?

Answer: It is 3 at position 1. The intervening 7 is larger. No value to the right exists, so the final element has no right match.

Related terms

Array
Range minimum query
Parallel algorithm
monotonic stack
amortised analysis
Cartesian tree
previous smaller element

Learn next

Trace the stack for an increasing sequence and a decreasing sequence. Count pushes and pops across the whole run. Then add equal values and explain why the strict comparison requires removing equal candidates.

Sources

Sources: Sitchinava and Svenning, The All Nearest Smaller Values Problem Revisited in Practice, Parallel and External Memory: https://algoparc.ics.hawaii.edu/pubs/p24-spaa.pdf . The definition and sequential stack discussion were reviewed. Berkman, Schieber and Vishkin's foundational paper is identified at https://doi.org/10.1006/jagm.1993.1018 ; its indexed abstract was reviewed, not its full text. The six-element example is original.

Previous: All Key relation Next: All-pairs testing