A monotonic stack is a last-in, first-out data structure whose stored values keep one order from bottom to top, either nondecreasing or nonincreasing. An incoming value can pop entries that would break that order before joining the stack. In market-data research, a single pass through a trade feed can label each trade with the first later trade of strictly larger size. Hong Kong Olympiad in Informatics, Data Structures (I)
Keep each unanswered trade on the stack
Take five fictional trade sizes in chronological order, measured in lots:
[4, 2, 2, 5, 3]. The question for each trade is which zero-based index first exceeds its size. Scanning from left to right, keep the indices of trades still waiting for an answer. Their sizes are nonincreasing from bottom to top, so the smallest pending size is always on top. Jackson State University, Finding the Next Greater ElementWhen a new trade arrives, pop from the top while the pending size is strictly smaller than the new size. For each pop, record the current index as the answer. Every popped trade was still waiting, so this arrival is its first qualifying one. Once the top size is at least as large as the new size, all sizes below it are at least as large too. Push the new index to keep the order intact.
Each column shows the pending stack after the new trade is processed. Dark blue marks the top.
The second 2-lot trade leaves the first 2-lot trade pending because the sizes tie. Both remain on the stack as separate indices. The 5-lot trade at index 3 then resolves indices 2, 1 and 0 in that pop order. The last trade is 3 lots, so it leaves the 5-lot trade pending and joins it on the stack. With
None for any unresolved index at the sample end, the result is [3, 3, 3, None, None].The Python list uses
append() to push and pop() to remove the top. Python tutorial, Using Lists as Stacksdef next_greater_indices(sizes: list[int]) -> list[int | None]:
"""Return the first later index with a strictly larger size."""
answers = [None] * len(sizes)
pending = []
for i, size in enumerate(sizes):
while pending and sizes[pending[-1]] < size:
answers[pending.pop()] = i
pending.append(i)
return answers
print(next_greater_indices([4, 2, 2, 5, 3]))
# [3, 3, 3, None, None]Linear work can arrive in a burst
Each index is pushed once and popped at most once. There is at most one final failed loop check per arrival. With constant-time comparisons and indexing and amortised constant-time stack operations, the full scan takes time. That is an amortised analysis: a single new trade can still pop a stack of order . A nonincreasing series fills the stack without a pop, so the worst-case extra stack space is even before counting the output.
Arrays, Linked Lists, Stacks, and Queues shows how an array or a linked list can implement the same stack operations. The link opens a public preview. The full lesson requires membership.
A label becomes known when the trade arrives
The first three observations have waits of 3, 2 and 1 later trades respectively. Those labels all become observable when index 3 arrives. Writing the wait back to each earlier row is valid when preparing historical targets. Feeding it into a decision at that row introduces look-ahead bias. A live process can emit those earlier rows' answers as they resolve, and a model fit at a historical cutoff can use only labels available by that cutoff. Here
None means the sample ended without a qualifying arrival. In a continuing feed, a larger trade can still arrive later. scikit-learn, Data leakage