webcoderspeed.com
53 articles
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.
Generate numRows rows of Pascal's triangle. Each interior element is the sum of the two elements above it.
Find the maximum product of a contiguous subarray. Track both min and max at each position (negative * negative = positive). O(n) time O(1) space.
Find the largest rectangle of 1s in a binary matrix by treating each row as a histogram and applying the Largest Rectangle in Histogram algorithm.
Minimize the largest sum among m subarrays by binary searching on the answer and greedy checking feasibility.
Find three non-overlapping subarrays of length k with maximum sum using sliding window sums and left/right best index arrays.
Find the longest valid parentheses substring using a stack that tracks the last unmatched index as a base.
Master 1D DP: Fibonacci/Climbing Stairs, House Robber, LIS, Coin Change, Jump Game, and Kadane patterns with 5-language templates.
Count ways to climb n stairs taking 1 or 2 steps. Classic Fibonacci DP — dp[n] = dp[n-1] + dp[n-2] with O(1) space.
Find minimum cost to reach the top of stairs. Each stair has a cost; you can take 1 or 2 steps. DP: min cost to reach each stair.
Maximize amount robbed without robbing adjacent houses. Classic skip-one DP: dp[i] = max(dp[i-1], dp[i-2] + nums[i]).
Houses arranged in a circle: first and last are adjacent. Run linear House Robber twice: once excluding last house, once excluding first.
Picking value k deletes all k-1 and k+1 elements. Map to House Robber: earn[k] = k * count(k), then max non-adjacent sum.
Find the contiguous subarray with the largest sum. Kadane's algorithm: either extend previous subarray or start fresh at current element.
Find maximum product of a contiguous subarray. Track both min and max at each position because a negative * negative becomes positive.
Find minimum coins to make amount. Unbounded knapsack DP: dp[amount] = min(dp[amount-coin]+1) over all coins. Bottom-up from 0 to amount.
Count number of combinations making up amount. Process each coin denomination completely (outer loop = coin) to avoid counting permutations.
Minimum perfect squares summing to n. Isomorphic to Coin Change where coins = all perfect squares ≤ n.
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.
Count ways to decode a digit string as letters (A=1,...,Z=26). DP: single digit + valid double digit transitions.
Check if string can be segmented into dictionary words. DP: dp[i]=true if some dp[j] is true and s[j:i] is in wordDict.
Find the length of the longest strictly increasing subsequence. O(n²) DP or O(n log n) patience sorting with binary search.
Maximum envelopes you can nest. Sort by width ascending and height descending, then LIS on heights. Descending heights prevents using same-width twice.
Count palindromic substrings. Expand around each center (n odd-length + n-1 even-length centers), count valid expansions.
Find longest palindromic subsequence length. 2D DP: if s[i]==s[j], dp[i][j] = dp[i+1][j-1]+2, else max of neighbors. Fill diagonally.
Can array be partitioned into two equal-sum subsets? 0/1 knapsack: can we pick some numbers summing to total/2? Bitset or DP boolean array.
Assign + or - to each number to reach target sum. DP counts ways to reach each sum. Reduces to 0/1 knapsack subset sum count.
LCS of two strings: dp[i][j] = LCS of first i chars of s1 and first j chars of s2. Full 2D DP treatment in the 2D DP section.
Complete 1D DP cheatsheet: 8 patterns, key transitions, complexity table, and problem index.
Master 2D DP: LCS, Edit Distance, grid path counting, matrix chain, interval DP, and stock patterns with 5-language templates.
Count paths from top-left to bottom-right moving only right or down. dp[i][j] = dp[i-1][j] + dp[i][j-1]. Math formula O(1) also works.
Count paths avoiding obstacle cells. Same DP but obstacles block cell (dp[i][j]=0) and obstacle at start/end returns 0.
Find minimum cost path from top-left to bottom-right moving right or down. dp[i][j] = grid[i][j] + min(dp[i-1][j], dp[i][j-1]).
Minimum path sum from top to bottom of triangle. Bottom-up DP: dp[j] = triangle[i][j] + min(dp[j], dp[j+1]).
Classic LCS: dp[i][j] = LCS length of s1[:i] and s2[:j]. If chars match add 1 to diagonal; else take max of skip either string.
Minimum operations (insert, delete, replace) to transform word1 to word2. Classic Wagner-Fischer 2D DP with O(n) space optimization.
Find shortest string containing both strings as subsequences. Length = len(s1)+len(s2)-LCS. Reconstruct by tracing DP table.
Maximize coins by bursting balloons. Key insight: think of last balloon burst in interval [i,j]. dp[i][j] = max coins from interval with k as last balloon.
Maximize profit from a single buy-sell. Track running minimum price; at each day profit = price - min_so_far.
Maximize profit with unlimited buy-sell transactions (but hold at most 1 share). Greedy: collect every upward slope.
Maximize profit with at most 2 transactions. Track 4 states: buy1, sell1, buy2, sell2. State machine DP.
At most k transactions. dp[t][i] = max profit using t transactions up to day i. If k >= n/2, unlimited transactions.
Unlimited transactions with 1-day cooldown after selling. 3-state DP: hold, sold (cooldown), rest.
Unlimited transactions with transaction fee per sell. 2-state DP: cash (not holding) and hold (holding stock).
Check if s3 is formed by interleaving s1 and s2. dp[i][j] = can s3[:i+j] be formed from s1[:i] and s2[:j].
Match string s against pattern p with . and *. dp[i][j] = does s[:i] match p[:j]. Handle * by matching zero or more of preceding char.
Match string with wildcard pattern: ? matches any char, * matches any sequence. Similar to regex but * matches any sequence (not zero/more of preceding).
Find minimum initial health to reach bottom-right dungeon cell. Solve backwards: dp[i][j] = min health needed at (i,j) to survive.
Find maximum strings using at most m zeros and n ones. 2D 0/1 knapsack: dp[i][j] = max strings using i zeros and j ones.
Find minimum sum falling path from top row to bottom row, moving to adjacent diagonal cells. DP row by row.
Minimum turns to print string where each turn prints a contiguous run of same char. Interval DP: dp[i][j] = min turns for s[i..j].
Complete 2D DP cheatsheet: 7 patterns, key transitions, stock state machine, interval DP template, and problem index.