59 articles
Master the Floyd-Warshall algorithm: a triple-nested DP that computes shortest paths between every pair of vertices in O(V^3), supports negative edges, and detects negative cycles. The interview workhorse for dense graphs and small V, asked at Google, Amazon, and Microsoft.
Master Bellman-Ford: relax every edge V-1 times to compute single-source shortest paths even with negative edges, and detect negative cycles in one extra pass. The algorithm behind LeetCode 787 Cheapest Flights Within K Stops, asked at Google, Amazon, and Meta.
Master longest path in a directed acyclic graph (DAG): a polynomial-time graph-DP that combines topological sort with memoised DFS. The same template solves LeetCode 329 Longest Increasing Path, course planning with prerequisites, and critical-path scheduling — a FAANG interview pattern at Google, Amazon, and Meta.
Master Pascal's Triangle (LeetCode 118 & 119) by understanding the binomial coefficient connection, the row-by-row DP pattern, space-optimized O(k) single-row generation, and five hidden mathematical properties that show up in Unique Paths, Coin Change, and beyond.
LeetCode 55 is a classic FAANG greedy problem that tests whether you can compress O(n²) DP thinking into a single O(n) pass. Learn the "max reachable index" insight, why greedy beats DP here, a full visual dry run, common traps, and every follow-up question interviewers ask next.
LeetCode 152 looks like a simple extension of Maximum Sum Subarray — until you hit negative numbers. A negative times a negative is positive, which means the current minimum can instantly become the new maximum. Learn why tracking BOTH cur_max and cur_min is the essential insight, how zeros act as hard resets, the four bugs every candidate makes, and step-by-step dry runs on key examples. Python and JavaScript solutions from O(n²) brute force to the elegant O(n) DP approach.
Master LeetCode 85 — Maximal Rectangle by building on LC 84 Largest Rectangle in Histogram. Learn the row-as-histogram insight, a visual row-by-row dry run, common pitfalls, and clean Python + JavaScript solutions that interviewers love.
Master LeetCode 410: learn why binary searching on the answer (not the array) is the key insight, walk through a full greedy feasibility check, and see both the DP and binary search solutions with line-by-line commentary.
Master LeetCode 689 with a full visual dry run, left/right DP insight, Python and JavaScript solutions, and real interview follow-ups on generalizing to k windows.
Master LC 871 with two complementary strategies: a greedy max-heap that asks "which station gives me the most fuel when I am stuck?" in O(n log n), and a DP table that asks "what is the farthest I can reach with exactly k stops?" in O(n²). Both are asked at Amazon and Google. Learn the intuition, see a full dry run, and understand when each approach fits.
LeetCode 32 is one of the most deceptive Hard problems on the platform — the brute-force is obvious, but all three optimal solutions require genuinely different mental models. Master the index-sentinel stack, the DP recurrence, and the two-pass counter sweep, and you will be able to answer any follow-up a FAANG interviewer throws at you.
LC 70 Climbing Stairs is the canonical introduction to 1D dynamic programming. The recurrence dp[n] = dp[n-1] + dp[n-2] is pure Fibonacci, and mastering why it works — recursion to memoization to tabulation — unlocks the entire family of staircase DP problems asked at Google, Amazon, and Meta.
LC 746 Min Cost Climbing Stairs extends the Climbing Stairs Fibonacci DP with per-step costs. The recurrence dp[i] = cost[i] + min(dp[i-1], dp[i-2]) computes the minimum total cost to leave each step. Asked at Amazon and Google as a direct test of whether you can adapt a known recurrence pattern under new constraints.
LC 198 House Robber asks you to maximize stolen money without robbing adjacent houses. The recurrence dp[i] = max(dp[i-1], dp[i-2] + nums[i]) is the canonical skip-one DP pattern asked at Amazon, Google, and Microsoft. Master the derivation, the three-phase DP evolution, and the O(1) space solution.
LC 213 House Robber II extends House Robber to a circular arrangement where the first and last houses are adjacent. The elegant solution runs the linear House Robber DP twice — once excluding the first house, once excluding the last — and returns the maximum. A top FAANG interview problem that tests systematic problem decomposition.
LC 740 Delete and Earn looks like a game problem but reduces to House Robber DP after a preprocessing step. Choosing value v earns v * count(v) points and forces deletion of v-1 and v+1, exactly the skip-adjacent constraint. Asked at Amazon and Meta to test whether candidates see through surface-level descriptions to the underlying DP pattern.
LC 53 Maximum Subarray is the foundational problem behind Kadane's Algorithm — a deceptively simple O(n) DP that asks: at each position, should I extend the current subarray or start fresh? Asked at Amazon, Google, and Microsoft and the basis for Maximum Product Subarray and other contiguous-subarray problems.
LC 152 Maximum Product Subarray extends Kadane's Algorithm by tracking both the running maximum and minimum products simultaneously. A negative number flips today's minimum into tomorrow's maximum. This dual-tracking insight is tested at Amazon, Google, and LinkedIn as a harder follow-up to Maximum Subarray.
LC 322 Coin Change finds the minimum number of coins to make a target amount using unlimited coin supply. The recurrence dp[i] = min(dp[i - coin] + 1) over all coins is the canonical unbounded knapsack minimization problem, asked at Amazon, Google, and Microsoft as a core DP interview question.
LC 518 Coin Change II counts the number of combinations (not permutations) of coins that sum to a target amount. The key insight is the loop order: coins outer, amounts inner. This unbounded knapsack counting pattern is tested at Amazon and Google to distinguish candidates who understand loop-order reasoning from those who memorize templates.
LC 279 Perfect Squares finds the minimum number of perfect square integers that sum to n. It is isomorphic to Coin Change (LC 322) where the "coins" are all perfect squares up to n. The DP recurrence dp[i] = min(dp[i - j*j] + 1) runs in O(n * sqrt(n)) time and is asked at Google and Amazon.
LC 55 Jump Game asks if you can reach the last index given maximum jump lengths. The DP approach is O(n^2) but the greedy insight — tracking the farthest reachable index — reduces it to O(n) O(1). Asked at Amazon and Google as a test of recognizing when greedy is provably optimal over DP.
LC 45 Jump Game II finds the minimum number of jumps to reach the last index. The DP solution is O(n^2), but the greedy window technique — extending the current reachable window whenever a boundary is crossed — achieves O(n) O(1). Asked at Amazon and Google as a harder follow-up to Jump Game.
LC 91 Decode Ways counts the number of ways to decode a digit string as letters A-Z. The recurrence combines one-digit and two-digit transitions — a conditional Fibonacci DP. Heavily tested at Amazon, Google, and Meta because it combines string parsing, edge case handling, and DP reasoning in a single problem.
LC 139 Word Break checks if a string can be segmented into dictionary words. The reachability DP dp[i] = true if some dp[j] is true and s[j:i] is in the dictionary. Asked heavily at Amazon, Google, and Microsoft as a test of string DP with set-based lookups.
LC 300 Longest Increasing Subsequence finds the length of the longest strictly increasing subsequence. The O(n²) DP is the expected starting point; the O(n log n) patience sorting binary search optimization is what FAANG interviewers look for. This problem is asked at Amazon, Google, and Microsoft and is the foundation for Russian Doll Envelopes.
LeetCode 354 Russian Doll Envelopes is a sneaky 2D Longest Increasing Subsequence problem. Sort by width ascending and height descending so equal widths cannot stack, then run patience-sort LIS on heights for an O(n log n) DP solution beloved by FAANG interviewers.
LeetCode 647 Palindromic Substrings is the canonical center-expansion problem. We derive the 2D DP recurrence, simplify it to expand-around-center for O(1) memory, and walk through a full DP table dry run with FAANG interview tips on why this beats Manacher in real interviews.
LeetCode 516 Longest Palindromic Subsequence is the cleanest interval DP recurrence in interview prep. We derive the dp[i][j] formulation, fill the table along diagonals, and reduce memory from O(n^2) to O(n) — exactly the depth Amazon and Google look for.
LeetCode 416 Partition Equal Subset Sum is the cleanest 0/1 knapsack disguise on the platform. We reduce it to subset-sum-equals-half, derive the boolean DP recurrence, walk through the reverse-iteration trick, and finish with a one-liner bitset version that crushes interviews.
LeetCode 494 Target Sum looks like sign-assignment but reduces to subset-sum count via a beautiful algebra trick. We derive the reduction, build the 1D DP, dry-run a tabulation, and discuss why this O(n * sum) solution beats 2^n brute force at FAANG.
LeetCode 1143 Longest Common Subsequence is the foundational two-string DP every FAANG interviewer expects you to nail. We derive the dp[i][j] recurrence, walk a full table, optimize space from O(m*n) to O(min(m,n)), and trace why this template powers Edit Distance, Shortest Common Supersequence, and diff tooling.
LC 62 Unique Paths is the foundational 2D grid DP problem at Amazon, Google, and Meta. Learn the recurrence, space-optimize to 1D, and master the combinatorics shortcut interviewers love to ask about.
LC 63 Unique Paths II extends the classic grid DP with obstacle cells. Master the obstacle-zeroing pattern, handle blocked start/end edge cases, and space-optimize to O(n) — the exact follow-up interviewers throw immediately after Unique Paths.
LC 64 Minimum Path Sum is the essential cost-minimization variant of grid DP, asked heavily at Amazon and Google. Learn the 2D recurrence, space-optimize to O(n), and understand why bottom-up tabulation handles borders without special-casing.
LC 120 Triangle asks for the minimum-sum path from apex to base. The bottom-up DP approach eliminates border initialization complexity and achieves O(n) space — a classic 2D DP problem that tests your ability to work on non-rectangular structures.
LC 1143 Longest Common Subsequence is the foundational sequence DP problem at every FAANG company. Master the 2D recurrence, space-optimize to O(n), and learn how to reconstruct the actual LCS — skills that transfer directly to Edit Distance, Shortest Common Supersequence, and Diff algorithms.
LC 72 Edit Distance (Levenshtein Distance) is the hard-level sequence DP benchmark at Google, Amazon, and Meta. Master the 3-operation recurrence, space-optimize to O(n), and understand how this algorithm powers spell-checkers, DNA alignment, and autocomplete systems.
LC 1092 Shortest Common Supersequence combines LCS computation with DP table reconstruction to produce the actual shortest string containing both inputs as subsequences. A hard-level 2D DP problem asked at Google and Amazon that demands both algorithm depth and reconstruction skill.
LC 312 Burst Balloons is the classic hard-level interval DP problem asked at Google, Amazon, and Meta. The key insight is thinking in reverse — instead of choosing which balloon to burst first, choose which one to burst last in each interval. This transforms an impossible ordering problem into clean O(n^3) DP.
LC 121 Best Time to Buy and Sell Stock is the foundational stock DP problem at every FAANG company. While solvable with a one-pass greedy approach, understanding its state machine formulation (hold/not-hold states) unlocks the full stock problem series from LC 122 through LC 714.
LC 122 Best Time to Buy and Sell Stock II allows unlimited buy-sell transactions (hold at most 1 share at a time). Solvable with a greedy slope-collection approach, but the state machine DP extension reveals how unlimited transactions differ structurally from single-transaction stock problems.
LC 123 Best Time to Buy and Sell Stock III limits transactions to at most 2. The state machine tracks 4 explicit states — buy1, sell1, buy2, sell2 — evolving each day through clean transitions. This is the hardest single-interview stock variant and the direct precursor to the k-transactions generalization in LC 188.
LC 188 Best Time to Buy and Sell Stock IV generalizes the stock problem to at most k transactions using a 2D DP table where dp[t][i] tracks the maximum profit using t transactions through day i. This is the hardest stock variant in FAANG interviews and requires combining the k-transaction state machine with the unlimited-transaction shortcut for large k.
LC 309 Best Time to Buy and Sell Stock with Cooldown adds a 1-day cooldown after selling. The state machine expands to 3 states — holding, sold (cooldown), and resting — and the buy transition reads from 2 days ago instead of 1 day ago. This structural change is the cleanest example of how constraints reshape state machine DP.
LC 714 Best Time to Buy and Sell Stock with Transaction Fee extends unlimited transactions by subtracting a fee on each sell. The state machine is identical to Stock II with one modification: the sell transition subtracts the fee. This is the final stock series variant and the cleanest demonstration that state machine DP is a modular framework.
LC 97 Interleaving String asks whether s3 can be formed by interleaving s1 and s2 while preserving character order. The 2D DP table dp[i][j] checks whether s3[:i+j] can be formed from s1[:i] and s2[:j] — a classic Boolean 2D DP problem asked at Google and Amazon.
LC 10 Regular Expression Matching implements "." (any char) and "*" (zero or more of preceding) using 2D DP. It is a Hard-level problem and the most complex string DP asked at Google and Meta — the star (*) handling requires 3 separate cases that trip up even experienced candidates.
LeetCode 44 Wildcard Matching is the classic 2D string DP question Meta and Google ask to test recurrence design under tricky base cases. We derive the dp[i][j] transitions for ? and *, dry-run a full table, and finish with a two-pointer optimization that drops memory to O(1).
LeetCode 174 Dungeon Game is the textbook example of why DP direction matters. We derive why forward DP fails, build the backward dp[i][j] = max(1, ...) recurrence, dry-run the grid, and finish with a space-optimized 1D solution loved at FAANG.
LeetCode 474 Ones and Zeroes is the cleanest two-capacity 0/1 knapsack on the platform. We derive the dp[i][j] recurrence, walk a full 2D table, and ship a 1D-collapsed solution that handles the dual-resource constraint while staying interview-friendly.
LeetCode 931 Minimum Falling Path Sum is the cleanest grid DP with diagonal moves. We derive the dp[i][j] recurrence with three predecessors, walk a full table, and ship an O(1) extra-space in-place tabulation that interviewers love.
LeetCode 664 Strange Printer is the canonical O(n^3) interval DP every senior FAANG interviewer expects you to handle. We derive the dp[i][j] recurrence, walk through the merge-on-match optimization, dry-run a full table, and discuss where Strange Printer sits in the Burst Balloons / MCM family.
LeetCode 264 (Medium) — generate the n-th ugly number using a min-heap with a dedupe set or a three-pointer DP merge that runs in pure O(n).
Week 2 of the FAANG mock program pairs Number of Islands and Longest Increasing Subsequence. Solve each correctly, then deliver one optimization upgrade and handle a live follow-up question — the pattern that separates "passes" from "strong hire" ratings.
Week 3 of the FAANG mock program pairs Burst Balloons and Word Ladder II as hard problems under timed pressure. Learn the stuck-recovery protocol, the inversion insight, and why partial credit plus continuous communication beats silence every time.
Count all longest increasing subsequences with DP in O(n^2) or with a segment tree on values for O(n log n). The classic crossover problem between DP and range-query data structures.
Solve LeetCode 1696 Jump Game VI with a monotonic deque to track the sliding window maximum of DP states in O(n). A high-signal FAANG interview problem.
Longest Palindromic Substring, Palindrome Partitioning, and Palindromic Substrings form a tight family of FAANG questions. Master expand-around-center, 2D DP, and the link to Manacher and you can adapt to any variant on the spot.