Monotonic stack: time and space complexity

High interview relevanceRoadmap: Intermediate

Time	O(n) total
Space	O(n)

Why it costs this much

Each index is pushed once and popped at most once, so the while loop inside the for loop does at most 2n operations in total.

Code

def next_greater(nums):
    res, stack = [-1] * len(nums), []
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x     # each index is popped at most once
        stack.append(i)              # and pushed exactly once
    return res

Common pitfalls

Decide whether the stack stays strictly or non-strictly ordered (< versus <=). That choice changes how ties behave.