dsa2 min read
Daily Temperatures [Medium] — Monotonic Stack
Find how many days until a warmer temperature for each day using a monotonic decreasing stack.
Read →
Monotonic-stack
38 articles
dsa2 min read
Sliding Window Maximum [Hard] — Monotonic Deque
Find the maximum in every sliding window of size k in O(n) using a monotonic decreasing deque.
Read →
dsa2 min read
Largest Rectangle in Histogram [Hard] — Monotonic Stack
Find the largest rectangle in a histogram in O(n) using a monotonic increasing stack that computes area when a shorter bar is encountered.
Read →
dsa4 min read
Greedy Algorithms & Monotonic Stack — Complete Guide
Master Greedy and Monotonic Stack: interval scheduling, activity selection, next greater/smaller element, largest rectangle, and trapping rain water.
Read →
dsa1 min read
Assign Cookies — Two-Pointer Greedy
Maximize children satisfied. Sort both greed and cookie sizes; greedily assign the smallest sufficient cookie to each child.
Read →
dsa1 min read
Non-overlapping Intervals — Interval Scheduling
Minimum removals to make intervals non-overlapping. Sort by end time; greedily keep earliest-ending intervals, count conflicts.
Read →
dsa1 min read
Minimum Number of Arrows to Burst Balloons
Find minimum arrows to burst all balloons (intervals). Sort by end; one arrow can burst all overlapping intervals. Count arrows needed.
Read →
dsa1 min read
Gas Station — Greedy Circular
Find starting gas station index to complete circular route. If total gas >= total cost, a solution exists. Track running balance; reset start when negative.
Read →
dsa1 min read
Candy — Two-Pass Greedy
Distribute minimum candies with higher-rated children getting more than neighbors. Two-pass: left-to-right for ascending, right-to-left for descending.
Read →
dsa1 min read
Next Greater Element I — Monotonic Stack
For each element in nums1, find next greater element in nums2. Monotonic stack + hashmap: process nums2, pop when greater found, store in map.
Read →
dsa1 min read
Daily Temperatures — Monotonic Stack Waiting Days
For each day find how many days until a warmer temperature. Monotonic decreasing stack of indices; pop when warmer temperature found.
Read →
dsa1 min read
Largest Rectangle in Histogram — Monotonic Stack
Find the area of the largest rectangle in a histogram. Monotonic increasing stack: when a shorter bar is found, pop and compute rectangle area using popped height and current width.
Read →
dsa1 min read
Trapping Rain Water — Two Pointer O(1) Space
Calculate water trapped between bars. Two-pointer approach: maintain max_left and max_right; water at each position = min(max_left, max_right) - height.
Read →
dsa1 min read
Remove Duplicate Letters — Greedy Monotonic Stack
Remove duplicates to get smallest lexicographic subsequence with all chars. Greedy: use monotonic stack, only pop if char appears later.
Read →
dsa1 min read
Remove K Digits — Greedy Monotonic Stack
Remove k digits to get smallest number. Monotonic increasing stack: pop larger digits when they appear before a smaller one. Remove remaining from end.
Read →
dsa1 min read
Sum of Subarray Minimums — Monotonic Stack Contribution
Sum of minimums of all subarrays. For each element, count how many subarrays have it as minimum using previous/next smaller element positions.
Read →
dsa1 min read
Maximum Width Ramp — Monotonic Stack + Two Pass
Find max j-i where i<j and nums[i]<=nums[j]. Build decreasing monotonic stack for left candidates, then scan from right to match.
Read →
dsa1 min read
132 Pattern — Monotonic Stack from Right
Find i<j<k where nums[i]<nums[k]<nums[j]. Scan right-to-left with decreasing stack; track max popped element as potential 'nums[k]' candidate.
Read →
dsa1 min read
Maximal Rectangle — Histogram per Row
Find the largest rectangle in a binary matrix. Build histogram row by row (reset to 0 on '0'), apply Largest Rectangle in Histogram each row.
Read →
dsa1 min read
Next Greater Element II — Circular Monotonic Stack
Next greater element in circular array. Iterate twice (2n) but use index mod n. Same decreasing stack pattern.
Read →
dsa1 min read
Minimum Cost to Connect Sticks — Min-Heap Greedy
Minimum cost to connect all sticks. Always connect the two cheapest (Huffman coding variant). Min-heap greedy: cost = sum of merged sticks each round.
Read →
dsa1 min read
Partition Labels — Greedy Interval Merge
Partition string so each letter appears in at most one part. Track last occurrence of each char; greedily extend current partition end.
Read →
dsa1 min read
Queue Reconstruction by Height — Greedy Sort + Insert
Reconstruct queue where [h,k] means person of height h has k taller/equal people in front. Sort by height desc (then k asc), insert at index k.
Read →
dsa1 min read
Jump Game VI — Greedy + Monotonic Deque
Maximum score to reach end where each jump is 1..k steps. Monotonic deque (sliding window maximum) of DP values for O(n) solution.
Read →
dsa1 min read
Max Chunks to Make Sorted — Greedy Max Tracking
Find max chunks of array that when sorted individually give fully sorted array. A chunk boundary exists when max(chunk so far) == current index.
Read →
dsa2 min read
Greedy & Monotonic Stack — Master Recap & Cheatsheet
Complete Greedy and Monotonic Stack cheatsheet: all patterns, templates, complexity table, and problem index.
Read →
dsa1 min read
Next Greater Node in Linked List — Monotonic Stack
Find the next greater value for each node in a linked list using a monotonic decreasing stack of indices.
Read →
dsa2 min read
Daily Temperatures — Monotonic Decreasing Stack
Find how many days until a warmer temperature using a monotonic decreasing stack of unresolved day indices.
Read →
dsa1 min read
Next Greater Element I — Monotonic Stack with HashMap
Find the next greater element for each query in O(n+m) using a monotonic stack on nums2 and a lookup map.
Read →
dsa1 min read
Next Greater Element II — Circular Array Monotonic Stack
Find the next greater element in a circular array by iterating twice (0 to 2n) and using a monotonic stack.
Read →
dsa1 min read
Online Stock Span — Monotonic Stack with Accumulated Span
Calculate the stock price span (consecutive days <= today) using a monotonic stack that accumulates spans.
Read →
dsa2 min read
Remove K Digits — Monotonic Increasing Stack
Remove k digits to form the smallest number by maintaining a monotonic increasing stack and greedy removal.
Read →
dsa2 min read
Sum of Subarray Minimums — Monotonic Stack with Contribution
Sum the minimums of all subarrays by computing each element's contribution as the minimum using previous and next smaller element spans.
Read →
dsa1 min read
132 Pattern — Monotonic Stack from Right
Detect a 132 pattern (i < j < k, nums[i] < nums[k] < nums[j]) using a monotonic stack scanning right to left.
Read →
dsa1 min read
Number of Visible People in Queue — Monotonic Stack
Count visible people in a queue for each person using a monotonic decreasing stack scanning right to left.
Read →
dsa1 min read
Largest Rectangle in Histogram — Monotonic Increasing Stack
Find the largest rectangle in a histogram by computing left and right boundaries using a monotonic increasing stack.
Read →
dsa1 min read
Maximal Rectangle — Histogram Stack on Each Row
Find the maximal rectangle in a binary matrix by building histogram heights row by row and applying largest rectangle.
Read →
dsa2 min read
Trapping Rain Water — Monotonic Stack Horizontal Layer
Calculate trapped rainwater volume using a monotonic stack that computes water in horizontal layers as bars are processed.
Read →