Maintain a Monotonic Stack

Practice Exercise Interview Easy Monotonic Stack

Checking your account…

Loading the interactive Practice workspace.If it does not appear, the problem and learning material remain readable, but browser execution is unavailable.Reload Practice workspace

Problem

Implement previous_smaller_indices(values). For every index, return the index of the nearest earlier value that is strictly smaller, or -1 when none exists. Maintain candidate indices in increasing-value order.

Starter code

def previous_smaller_indices(values):
    pass

Test cases

rises-and-drops

{
  "args": [
    [
      3,
      1,
      4,
      2,
      5
    ]
  ]
}

Expected: [-1,-1,1,1,3]

equal-values

{
  "args": [
    [
      2,
      2,
      3
    ]
  ]
}

Expected: [-1,-1,1]

Wizard outline

Step 1: Create candidate-index state
Initialize an empty stack and result list. The stack contains only earlier indices that may answer a later query.
Step 2: Read the nearest increasing candidate
Use the stack top as the nearest smaller earlier index when values rise. On strictly increasing input, every previous index remains a valid candidate and the nearest is the latest one.
Step 3: Pop larger candidates
Remove earlier indices whose values are greater than the current value. A larger top cannot answer the current item and is dominated by the newer, smaller value for future items.
Step 4: Pop equal candidates for strictness
Remove equal values because the answer must be strictly smaller. An equal earlier value is not a valid answer and would hide a smaller candidate beneath it.

Footguns and prerequisites

Popping only greater values leaves an equal value even though the required predecessor must be strictly smaller.
Storing values instead of indices loses the location that the result must report.
arrays strings two pointers sliding window

Reviewed references

Python More on Lists

Prepared Interview Problems

Car Fleet(opens in a new tab)
Maintain a Monotonic Stack isolates stack indices increase from bottom to top and their values are strictly increasing after invalid candidates are removed. That focused state discipline is required when implementing car fleet as a complete Interview Problem.
Daily Temperatures(opens in a new tab)
Maintain a Monotonic Stack isolates stack indices increase from bottom to top and their values are strictly increasing after invalid candidates are removed. That focused state discipline is required when implementing daily temperatures as a complete Interview Problem.

Recommended approach and implementation

Nearest earlier elements under an ordering constraint can discard candidates permanently as soon as a later value dominates them. Stack indices increase from bottom to top and their values are strictly increasing after invalid candidates are removed.

Why it works: After removing earlier indices whose values are not strictly smaller, the stack top is the nearest earlier index with a strictly smaller value. Appending that index, or -1 when the stack is empty, therefore gives the exact previous-smaller result.

def previous_smaller_indices(values):
    stack = []
    result = []
    for index, value in enumerate(values):
        while stack and values[stack[-1]] >= value:
            stack.pop()
        result.append(stack[-1] if stack else -1)
        stack.append(index)
    return result