Stacks

Nested Objects

Nearest Smaller Values

stack = []
res = []
for item in collection:
    while stack and stack[-1] >= item:
        # pop recent items that is larger than the current one
        stack.pop()

    if stack: # this is the nearest smaller item (to the left)
        res.append(stack[-1])
    else: # there is no such item
        res.append(None)

    stack.append(item)

Properties

  • The stack is sorted in the ascending order for finding the nearest smaller values. Hence, Binary Search can be applied on the stack to quickly retrieve the value sastifying a condition.

Problems