webcoderspeed.com
68 articles
The classic stock problem asked at Amazon, Google and Microsoft. Learn the O(n) greedy "min so far" approach with complete solutions in C, C++, Java, JavaScript and Python, plus extensions to Stock II, III and IV.
Kadane's Algorithm is a must-know pattern for FAANG interviews. Solve Maximum Subarray in O(n) time with full solutions in C, C++, Java, JavaScript and Python, plus divide-and-conquer O(n log n) alternative.
Find two lines that together with the x-axis form a container holding the most water. Greedy two-pointer O(n) — never check a pair that can't be optimal.
Determine if you can reach the last index. Greedy: track maximum reachable index. If current position exceeds max reach, return false. O(n) O(1).
Insert a new interval into a sorted non-overlapping list and merge any overlaps in a single sweep.
Find the minimum number of intervals to remove so the rest are non-overlapping, using a greedy earliest-end-time strategy.
Determine if there exists an increasing subsequence of length 3 using two greedy variables in O(n) time O(1) space.
Find minimum number of jumps to reach the last index using greedy BFS-style level tracking.
Determine the unique starting gas station for a circular route using a greedy one-pass algorithm.
Partition a string into the maximum number of parts where each letter appears in at most one part, using last occurrence mapping.
Calculate minimum CPU intervals for tasks with cooldown using a greedy formula based on the most frequent task count.
Find the minimum arrows needed to burst all balloons arranged as intervals using a greedy sort-by-end approach.
Maximize a number by making at most one swap, using a last-occurrence map to find the optimal swap greedily.
Distribute minimum candies so each child with higher rating than neighbors gets more, using left-to-right then right-to-left passes.
Rearrange nums to maximize advantage over B using a greedy strategy: assign the smallest winning card, else discard the smallest.
Find the minimum refueling stops to reach target by greedily picking the largest fuel station passed so far whenever we run out.
Find the minimum rotations to make all tops or bottoms equal by checking if a target value (from first domino) can unify the entire row.
Reconstruct the stamp sequence in reverse by greedily finding where the stamp can overwrite current characters in the target string.
Maximize the minimum distance between m balls in baskets using binary search on the answer (minimum distance).
Minimize the maximum value after performing k operations (average adjacent elements) using binary search on the answer.
Maximize events attended by greedily attending the event with the earliest end date each day using binary search.
Check if you can reach the last index. Greedy: track furthest reachable index. If current position > reach, stuck.
Find minimum jumps to reach the last index. Greedy: at each jump boundary, extend to the farthest reachable position.
Master Greedy and Monotonic Stack: interval scheduling, activity selection, next greater/smaller element, largest rectangle, and trapping rain water.
Maximize children satisfied. Sort both greed and cookie sizes; greedily assign the smallest sufficient cookie to each child.
Minimum removals to make intervals non-overlapping. Sort by end time; greedily keep earliest-ending intervals, count conflicts.
Find minimum arrows to burst all balloons (intervals). Sort by end; one arrow can burst all overlapping intervals. Count arrows needed.
Find starting gas station index to complete circular route. If total gas >= total cost, a solution exists. Track running balance; reset start when negative.
Distribute minimum candies with higher-rated children getting more than neighbors. Two-pass: left-to-right for ascending, right-to-left for descending.
For each element in nums1, find next greater element in nums2. Monotonic stack + hashmap: process nums2, pop when greater found, store in map.
For each day find how many days until a warmer temperature. Monotonic decreasing stack of indices; pop when warmer temperature found.
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.
Calculate water trapped between bars. Two-pointer approach: maintain max_left and max_right; water at each position = min(max_left, max_right) - height.
Remove duplicates to get smallest lexicographic subsequence with all chars. Greedy: use monotonic stack, only pop if char appears later.
Remove k digits to get smallest number. Monotonic increasing stack: pop larger digits when they appear before a smaller one. Remove remaining from end.
Sum of minimums of all subarrays. For each element, count how many subarrays have it as minimum using previous/next smaller element positions.
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.
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.
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.
Next greater element in circular array. Iterate twice (2n) but use index mod n. Same decreasing stack pattern.
Minimum cost to connect all sticks. Always connect the two cheapest (Huffman coding variant). Min-heap greedy: cost = sum of merged sticks each round.
Partition string so each letter appears in at most one part. Track last occurrence of each char; greedily extend current partition end.
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.
Maximum score to reach end where each jump is 1..k steps. Monotonic deque (sliding window maximum) of DP values for O(n) solution.
Find max chunks of array that when sorted individually give fully sorted array. A chunk boundary exists when max(chunk so far) == current index.
Complete Greedy and Monotonic Stack cheatsheet: all patterns, templates, complexity table, and problem index.
Determine if cards can be rearranged into consecutive groups of size groupSize using a sorted frequency map.
Find minimum CPU intervals to schedule tasks with cooldown using a greedy max-heap simulation.
Rearrange a string so no two adjacent characters are the same using a greedy max-heap approach.
Maximize courses taken within deadlines by greedily scheduling and swapping out the longest past course.
Find minimum cost to connect all sticks by greedily always merging the two shortest sticks first.
Maximize capital after k IPO investments by greedily picking the highest profit project among affordable ones.
Greedily use ladders for the largest climbs and bricks for smaller gaps, managed with a min-heap of ladder sizes.
Find minimum fuel stops to reach the target by greedily selecting the largest available fuel stations when running low.
Maximize team performance (sum of speeds * min efficiency) by sorting by efficiency and using a min-heap on speeds.
Build the longest string with at most 2 consecutive identical characters by always using the most frequent available character.
Minimize max-min of an array by doubling odd numbers and repeatedly halving the max using a max-heap.
Find the minimum number of elements to remove to reduce array size by half by greedily removing most frequent elements.
Remove k digits to form the smallest number by maintaining a monotonic increasing stack and greedy removal.
Find the minimum intervals to execute all tasks with cooldown n by greedily scheduling the most frequent task first.
Find minimum cameras to monitor all nodes using greedy bottom-up: prefer placing cameras at parents of uncovered leaves.
Maximize water trapped between two vertical lines using inward two pointers that always move the shorter line inward.
Find minimum boats to save everyone where each boat carries at most 2 people with total weight <= limit, using sort + greedy two pointers.
Check if an array can be split into three consecutive parts with equal sum using a greedy counting approach.
Find the minimum spanning tree of a weighted graph using Kruskal's algorithm. Sort edges by weight, use Union-Find to avoid cycles. O(E log E) time.
Build the minimum spanning tree using Prim's algorithm: start from any vertex, greedily expand by always adding the minimum-weight crossing edge using a min-heap.
Add minimum characters to the front of a string to make it a palindrome. KMP trick: concatenate s + '#' + rev(s), find the LPS value at the last position.
Find the minimum intervals to complete all tasks given cooldown n. Greedy with max-heap: always execute most frequent available task, idle only when forced.