dsa1 min read
Delete and Earn — House Robber on Frequency Array
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.
Read →
All Posts
1575 articles
dsa1 min read
Maximum Subarray — Kadane's Algorithm
Find the contiguous subarray with the largest sum. Kadane's algorithm: either extend previous subarray or start fresh at current element.
Read →
dsa1 min read
Maximum Product Subarray — Kadane with Min/Max
Find maximum product of a contiguous subarray. Track both min and max at each position because a negative * negative becomes positive.
Read →
dsa2 min read
Coin Change — Unbounded Knapsack DP
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.
Read →
dsa1 min read
Coin Change II — Count Ways Unbounded Knapsack
Count number of combinations making up amount. Process each coin denomination completely (outer loop = coin) to avoid counting permutations.
Read →
Page 95 of 315