Loading
Loading
A stack kept in sorted order answers "next greater" in one pass.
Push indices onto a stack, but before each push pop everything that the new element makes irrelevant. The stack therefore stays sorted, and the moment an element is popped you have discovered its next greater — or smaller — neighbour. Each element is pushed once and popped once, so the whole sweep is linear despite the inner loop.
Popping is the discovery event, not a cleanup step. When you pop element x because y arrived, you have just learned that y is x's next greater element. Write the answer at that moment.
The shape, not a solution. Adapt the condition and the state to the problem in front of you.
def next_greater(nums): """For each index, the value of the next strictly greater element.""" result = [-1] * len(nums) stack = [] # holds indices; their values are strictly decreasing for index, value in enumerate(nums): # Everything smaller than the new value has just found its answer. while stack and nums[stack[-1]] < value: result[stack.pop()] = value stack.append(index) # Whatever remains never found a greater element; it keeps -1. return result def previous_smaller(nums): """Mirror image: scan the same way, keep the stack increasing.""" result = [-1] * len(nums) stack = [] for index, value in enumerate(nums): while stack and nums[stack[-1]] >= value: stack.pop() result[index] = nums[stack[-1]] if stack else -1 stack.append(index) return result| Status | Problem | Difficulty | Role |
|---|---|---|---|
| Warmest Day Ahead#6 | Medium | Primary | |
| Valid Nesting#15 | Easy | Primary | |
| Evaluate a Postfix Formula#42 | Medium | Primary | |
Sign in to keep a note here. It is free, and nobody else can see it.
Sign in| Stack With Instant Minimum#43 |
| Medium |
| Primary |
| Queue From Two Stacks#44 | Medium | Primary |
| Collapse Adjacent Duplicates#45 | Easy | Primary |
| Rolling Peak#46 | Hard | Primary |