Quick Overview
A monotonic stack discards anything the incoming element beats, so its contents stay ordered. Each item is pushed and popped at most once, which is why "next greater element" is `O(N)` and not `O(N^2)`.
A Stack is an abstract linear data structure that restricts insertions and deletions to a single end called the top:
push(x): Place item onto top of stack (O(1)).pop(): Remove and return topmost item (O(1)).peek(): Inspect topmost item without removing (O(1)).Verify that all opening brackets have corresponding matching closing brackets in the correct order:
function isValidParentheses(s) {
const stack = [];
const bracketMap = { ")": "(", "}": "{", "]": "[" };
for (const char of s) {
if (char === "(" || char === "{" || char === "[") {
stack.push(char); // Push opening brackets
} else if (bracketMap[char]) {
// Pop matching bracket from top of stack
if (stack.pop() !== bracketMap[char]) {
return false;
}
}
}
return stack.length === 0; // Stack must be completely empty!
}
console.log(isValidParentheses("({[]})")); // Output: true
console.log(isValidParentheses("([)]")); // Output: false
A Monotonic Stack keeps its elements in strictly ascending or descending order. It solves "Next Greater Element" and "Daily Temperatures" problems in linear O(N) time!
function nextGreaterElement(nums) {
const result = new Array(nums.length).fill(-1);
const stack = []; // Stores indices of elements
for (let i = 0; i < nums.length; i++) {
// While current element is greater than element at top of stack
while (stack.length > 0 && nums[i] > nums[stack[stack.length - 1]]) {
const prevIndex = stack.pop();
result[prevIndex] = nums[i]; // Found next greater element!
}
stack.push(i);
}
return result;
}
console.log(nextGreaterElement([2, 1, 2, 4, 3])); // Output: [4, 2, 4, -1, -1]
pop() on an empty stack returns undefined, which can cause subtle comparison bugs if not guarded."(()"), returning true is wrong. Check stack.length === 0.Use stacks for nested evaluations and parser syntax trees. Next, let's explore Queues, Deques, and Ring Buffers!
Big O describes how work grows, not how long it takes. An `O(N^2)` algorithm on 1,000 items does a million steps; the same work at `O(N log N)` does about 10,000.
A dynamic array doubles rather than growing by one, so the expensive copy lands on the 1st, 2nd, 4th and 8th push. Averaged across every push, that is `O(1)` amortised.
A nested loop tests every pair in `O(N^2)`. On sorted data, moving two pointers inward from both ends rules out half the remaining candidates at each step and settles it in one `O(N)` pass.