Intermediate LevelData Structures & Algorithms
What is a Monotonic Stack and how does it solve Next Greater Element?
ā Interview Prompt: Explain Monotonic Stack (increasing/decreasing), Next Greater Element, and Daily Temperatures problems in O(N).
A Monotonic Stack maintains elements in strictly increasing or decreasing order. When a new element violates the order, it pops all elements it is greater (or smaller) than, resolving those elements' answers.
Next Greater Element: $O(N)$
Maintain a decreasing stack of indices. When element $A[i]$ is greater than stack.top, pop the top ā $A[i]$ is its next greater element!
Code Implementation Example
typescript
// Next Greater Element ā O(N)
function nextGreaterElement(nums: number[]): number[] {
const result = new Array(nums.length).fill(-1);
const stack: number[] = []; // stores indices, decreasing values
for (let i = 0; i < nums.length; i++) {
// Pop all elements smaller than nums[i]
while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
result[stack.pop()!] = nums[i]; // nums[i] is NGE for popped index
}
stack.push(i);
}
return result;
}
console.log(nextGreaterElement([2, 1, 2, 4, 3]));
// [-1 from left] ā [4, 2, 4, -1, -1]š”Monotonic decreasing stack solving Next Greater Element in O(N).
šÆ Interview Key Takeaway
Monotonic stacks solve "next greater/smaller" patterns in O(N). Each element is pushed and popped at most once. Used in stock span, histogram, trap rain water.
#DSA#Monotonic Stack#Stack#Patterns#Intermediate
Back to all Data Structures & Algorithms Questionsā