Question Bank
Monotonic Stack Patterns
Difficulty: Medium
Five prompts on monotonic stacks for next-greater-element, daily temperatures, and largest rectangle. Mostly implementation with one trace and one bug hunt.
Monotonic Stack Patterns
Five prompts on monotonic stacks for next-greater-element, daily temperatures, and largest rectangle. Mostly implementation with one trace and one bug hunt.
811 views
23
Implement nextGreaterElement(nums) returning an array where out[i] is the next strictly greater value to the right of nums[i], or -1 if none. Aim for O(n).
Examples
Example 1:
Input: nums = [2, 1, 2, 4, 3]
Output: [4, 2, 4, -1, -1]
Explanation: Walk left to right with a stack of indices. For each new value, pop indices whose values are strictly smaller; they have just found their next-greater (current value). Push the current index. The remaining stack at the end gets -1.Implement dailyTemperatures(temps) returning an array out where out[i] is the number of days until a strictly warmer temperature, or 0 if none.
Examples
Example 1:
Input: temps = [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]
Explanation: Same monotonic-stack-of-indices pattern as next-greater. For each new day, pop indices with strictly smaller temperatures and write out[j] = i - j. Days that never see a warmer follow-up stay at 0.Trace it. Run nextGreaterElement([2, 1, 3]) step by step. List the stack contents and out after each iteration.
Examples
Example 1:
Input: nums = [2, 1, 3]
Output: [3, 3, -1]
Explanation: i = 0: push 0, stack [0]. i = 1: nums[0] = 2 >= 1, no pops, push 1, stack [0, 1]. i = 2: nums[1] = 1 < 3, pop 1, out[1] = 3. nums[0] = 2 < 3, pop 0, out[0] = 3. Push 2, stack [2]. Final out = [3, 3, -1].When does a monotonic stack maintain a non-decreasing vs a non-increasing stack? Give one canonical problem for each.
Spot the bug. This prevGreaterOrEqual(nums) is meant to return, for each index, the previous greater-or-equal value (or -1 if none). It returns the wrong answer on inputs that contain repeated values.
Examples
Example 1:
Input: nums = [3, 3]
Output (buggy version): [-1, -1]
Output (fixed version): [-1, 3]
Explanation: The buggy pop condition stack.top <= nums[i] also pops equal values, but an equal predecessor is a valid 'greater-or-equal' answer. The fix pops only when stack.top < nums[i].