Problem: You are climbing a staircase. It takes n steps to reach the top. Each time you can climb 1 or 2 steps. In how many distinct ways can you climb to the top?
function climbStairs(n) {
if (n <= 2) return n;
return climbStairs(n - 1) + climbStairs(n - 2);
}
// Time: O(2^n), Space: O(n)function climbStairs(n) {
const memo = new Map();
function dp(n) {
if (n <= 2) return n;
if (memo.has(n)) return memo.get(n);
const result = dp(n - 1) + dp(n - 2);
memo.set(n, result);
return result;
}
return dp(n);
}
// Time: O(n), Space: O(n)function climbStairs(n) {
if (n <= 2) return n;
const dp = new Array(n + 1);
dp[1] = 1;
dp[2] = 2;
for (let i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}
// Time: O(n), Space: O(n)function climbStairs(n) {
if (n <= 2) return n;
let prev2 = 1, prev1 = 2;
for (let i = 3; i <= n; i++) {
const current = prev1 + prev2;
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// Time: O(n), Space: O(1)Problem: You are a robber planning to rob houses along a street. Each house has a certain amount of money. Adjacent houses have security systems connected. Determine the maximum amount you can rob without alerting the police.
function rob(nums) {
function dp(i) {
if (i < 0) return 0;
if (i === 0) return nums[0];
return Math.max(dp(i - 1), nums[i] + dp(i - 2));
}
return dp(nums.length - 1);
}
// Time: O(2^n), Space: O(n)function rob(nums) {
const memo = new Map();
function dp(i) {
if (i < 0) return 0;
if (i === 0) return nums[0];
if (memo.has(i)) return memo.get(i);
const result = Math.max(dp(i - 1), nums[i] + dp(i - 2));
memo.set(i, result);
return result;
}
return dp(nums.length - 1);
}
// Time: O(n), Space: O(n)function rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
const dp = new Array(nums.length);
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
dp[i] = Math.max(dp[i - 1], nums[i] + dp[i - 2]);
}
return dp[nums.length - 1];
}
// Time: O(n), Space: O(n)function rob(nums) {
if (nums.length === 0) return 0;
if (nums.length === 1) return nums[0];
let prev2 = nums[0];
let prev1 = Math.max(nums[0], nums[1]);
for (let i = 2; i < nums.length; i++) {
const current = Math.max(prev1, nums[i] + prev2);
prev2 = prev1;
prev1 = current;
}
return prev1;
}
// Time: O(n), Space: O(1)Problem: You are given an array cost where cost[i] is the cost of the ith step. You can start from step 0 or step 1. Find minimum cost to reach the top.
function minCostClimbingStairs(cost) {
function dp(i) {
if (i < 0) return 0;
if (i === 0 || i === 1) return cost[i];
return cost[i] + Math.min(dp(i - 1), dp(i - 2));
}
const n = cost.length;
return Math.min(dp(n - 1), dp(n - 2));
}
// Time: O(2^n), Space: O(n)function minCostClimbingStairs(cost) {
const memo = new Map();
function dp(i) {
if (i < 0) return 0;
if (i === 0 || i === 1) return cost[i];
if (memo.has(i)) return memo.get(i);
const result = cost[i] + Math.min(dp(i - 1), dp(i - 2));
memo.set(i, result);
return result;
}
const n = cost.length;
return Math.min(dp(n - 1), dp(n - 2));
}
// Time: O(n), Space: O(n)function minCostClimbingStairs(cost) {
const n = cost.length;
const dp = new Array(n);
dp[0] = cost[0];
dp[1] = cost[1];
for (let i = 2; i < n; i++) {
dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);
}
return Math.min(dp[n - 1], dp[n - 2]);
}
// Time: O(n), Space: O(n)function minCostClimbingStairs(cost) {
const n = cost.length;
let prev2 = cost[0];
let prev1 = cost[1];
for (let i = 2; i < n; i++) {
const current = cost[i] + Math.min(prev1, prev2);
prev2 = prev1;
prev1 = current;
}
return Math.min(prev1, prev2);
}
// Time: O(n), Space: O(1)Problem: A robot is located at the top-left corner of an m x n grid. The robot can only move down or right. How many possible unique paths are there to reach bottom-right?
function uniquePaths(m, n) {
function dp(row, col) {
if (row === 0 || col === 0) return 1;
return dp(row - 1, col) + dp(row, col - 1);
}
return dp(m - 1, n - 1);
}
// Time: O(2^(m+n)), Space: O(m+n)function uniquePaths(m, n) {
const memo = new Map();
function dp(row, col) {
if (row === 0 || col === 0) return 1;
const key = `${row},${col}`;
if (memo.has(key)) return memo.get(key);
const result = dp(row - 1, col) + dp(row, col - 1);
memo.set(key, result);
return result;
}
return dp(m - 1, n - 1);
}
// Time: O(m*n), Space: O(m*n)function uniquePaths(m, n) {
const dp = Array(m).fill(0).map(() => Array(n).fill(0));
// Base case: first row and column
for (let i = 0; i < m; i++) dp[i][0] = 1;
for (let j = 0; j < n; j++) dp[0][j] = 1;
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
// Time: O(m*n), Space: O(m*n)function uniquePaths(m, n) {
let prev = Array(n).fill(1);
for (let i = 1; i < m; i++) {
const curr = Array(n).fill(0);
curr[0] = 1;
for (let j = 1; j < n; j++) {
curr[j] = curr[j - 1] + prev[j];
}
prev = curr;
}
return prev[n - 1];
}
// Time: O(m*n), Space: O(n)Problem: Given an m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path.
function minPathSum(grid) {
const m = grid.length, n = grid[0].length;
function dp(row, col) {
if (row === 0 && col === 0) return grid[0][0];
if (row < 0 || col < 0) return Infinity;
return grid[row][col] + Math.min(dp(row - 1, col), dp(row, col - 1));
}
return dp(m - 1, n - 1);
}
// Time: O(2^(m+n)), Space: O(m+n)function minPathSum(grid) {
const m = grid.length, n = grid[0].length;
const memo = new Map();
function dp(row, col) {
if (row === 0 && col === 0) return grid[0][0];
if (row < 0 || col < 0) return Infinity;
const key = `${row},${col}`;
if (memo.has(key)) return memo.get(key);
const result = grid[row][col] + Math.min(dp(row - 1, col), dp(row, col - 1));
memo.set(key, result);
return result;
}
return dp(m - 1, n - 1);
}
// Time: O(m*n), Space: O(m*n)function minPathSum(grid) {
const m = grid.length, n = grid[0].length;
const dp = Array(m).fill(0).map(() => Array(n).fill(0));
dp[0][0] = grid[0][0];
// First row
for (let j = 1; j < n; j++) {
dp[0][j] = dp[0][j - 1] + grid[0][j];
}
// First column
for (let i = 1; i < m; i++) {
dp[i][0] = dp[i - 1][0] + grid[i][0];
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
dp[i][j] = grid[i][j] + Math.min(dp[i - 1][j], dp[i][j - 1]);
}
}
return dp[m - 1][n - 1];
}
// Time: O(m*n), Space: O(m*n)function minPathSum(grid) {
const m = grid.length, n = grid[0].length;
let prev = Array(n).fill(0);
prev[0] = grid[0][0];
// First row
for (let j = 1; j < n; j++) {
prev[j] = prev[j - 1] + grid[0][j];
}
for (let i = 1; i < m; i++) {
const curr = Array(n).fill(0);
curr[0] = prev[0] + grid[i][0];
for (let j = 1; j < n; j++) {
curr[j] = grid[i][j] + Math.min(prev[j], curr[j - 1]);
}
prev = curr;
}
return prev[n - 1];
}
// Time: O(m*n), Space: O(n)Problem: Same as Unique Paths, but now the grid has obstacles. An obstacle is marked as 1 and empty space is marked as 0.
function uniquePathsWithObstacles(grid) {
const m = grid.length, n = grid[0].length;
function dp(row, col) {
if (row < 0 || col < 0 || grid[row][col] === 1) return 0;
if (row === 0 && col === 0) return 1;
return dp(row - 1, col) + dp(row, col - 1);
}
return dp(m - 1, n - 1);
}
// Time: O(2^(m+n)), Space: O(m+n)function uniquePathsWithObstacles(grid) {
const m = grid.length, n = grid[0].length;
const memo = new Map();
function dp(row, col) {
if (row < 0 || col < 0 || grid[row][col] === 1) return 0;
if (row === 0 && col === 0) return 1;
const key = `${row},${col}`;
if (memo.has(key)) return memo.get(key);
const result = dp(row - 1, col) + dp(row, col - 1);
memo.set(key, result);
return result;
}
return dp(m - 1, n - 1);
}
// Time: O(m*n), Space: O(m*n)function uniquePathsWithObstacles(grid) {
const m = grid.length, n = grid[0].length;
if (grid[0][0] === 1 || grid[m - 1][n - 1] === 1) return 0;
const dp = Array(m).fill(0).map(() => Array(n).fill(0));
dp[0][0] = 1;
// First row
for (let j = 1; j < n; j++) {
dp[0][j] = grid[0][j] === 1 ? 0 : dp[0][j - 1];
}
// First column
for (let i = 1; i < m; i++) {
dp[i][0] = grid[i][0] === 1 ? 0 : dp[i - 1][0];
}
for (let i = 1; i < m; i++) {
for (let j = 1; j < n; j++) {
if (grid[i][j] === 1) {
dp[i][j] = 0;
} else {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
}
return dp[m - 1][n - 1];
}
// Time: O(m*n), Space: O(m*n)function uniquePathsWithObstacles(grid) {
const m = grid.length, n = grid[0].length;
if (grid[0][0] === 1 || grid[m - 1][n - 1] === 1) return 0;
let prev = Array(n).fill(0);
prev[0] = 1;
// First row
for (let j = 1; j < n; j++) {
prev[j] = grid[0][j] === 1 ? 0 : prev[j - 1];
}
for (let i = 1; i < m; i++) {
const curr = Array(n).fill(0);
curr[0] = grid[i][0] === 1 ? 0 : prev[0];
for (let j = 1; j < n; j++) {
if (grid[i][j] === 1) {
curr[j] = 0;
} else {
curr[j] = prev[j] + curr[j - 1];
}
}
prev = curr;
}
return prev[n - 1];
}
// Time: O(m*n), Space: O(n)Problem: Given a string s, return the longest palindromic substring in s.
function longestPalindrome(s) {
let longest = '';
function expandAroundCenter(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
left--;
right++;
}
return s.slice(left + 1, right);
}
for (let i = 0; i < s.length; i++) {
const odd = expandAroundCenter(i, i);
const even = expandAroundCenter(i, i + 1);
const longer = odd.length > even.length ? odd : even;
if (longer.length > longest.length) {
longest = longer;
}
}
return longest;
}
// Time: O(n^2), Space: O(1)function longestPalindrome(s) {
const n = s.length;
const dp = Array(n).fill(false).map(() => Array(n).fill(false));
let start = 0, maxLen = 1;
// Every single character is a palindrome
for (let i = 0; i < n; i++) {
dp[i][i] = true;
}
// Check for length 2
for (let i = 0; i < n - 1; i++) {
if (s[i] === s[i + 1]) {
dp[i][i + 1] = true;
start = i;
maxLen = 2;
}
}
// Check for lengths greater than 2
for (let len = 3; len <= n; len++) {
for (let i = 0; i <= n - len; i++) {
const j = i + len - 1;
if (s[i] === s[j] && dp[i + 1][j - 1]) {
dp[i][j] = true;
start = i;
maxLen = len;
}
}
}
return s.substring(start, start + maxLen);
}
// Time: O(n^2), Space: O(n^2)function longestPalindrome(s) {
if (s.length < 2) return s;
let start = 0, maxLen = 0;
function expand(left, right) {
while (left >= 0 && right < s.length && s[left] === s[right]) {
const currentLen = right - left + 1;
if (currentLen > maxLen) {
start = left;
maxLen = currentLen;
}
left--;
right++;
}
}
for (let i = 0; i < s.length; i++) {
expand(i, i); // odd length palindromes
expand(i, i + 1); // even length palindromes
}
return s.substring(start, start + maxLen);
}
// Time: O(n^2), Space: O(1)Problem: Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of dictionary words.
function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
function dp(start) {
if (start === s.length) return true;
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (wordSet.has(word) && dp(end)) {
return true;
}
}
return false;
}
return dp(0);
}
// Time: O(2^n), Space: O(n)function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const memo = new Map();
function dp(start) {
if (start === s.length) return true;
if (memo.has(start)) return memo.get(start);
for (let end = start + 1; end <= s.length; end++) {
const word = s.slice(start, end);
if (wordSet.has(word) && dp(end)) {
memo.set(start, true);
return true;
}
}
memo.set(start, false);
return false;
}
return dp(0);
}
// Time: O(n^2), Space: O(n)function wordBreak(s, wordDict) {
const wordSet = new Set(wordDict);
const n = s.length;
const dp = Array(n + 1).fill(false);
dp[0] = true; // empty string
for (let i = 1; i <= n; i++) {
for (let j = 0; j < i; j++) {
if (dp[j] && wordSet.has(s.slice(j, i))) {
dp[i] = true;
break;
}
}
}
return dp[n];
}
// Time: O(n^2), Space: O(n)For this problem, the bottom-up solution is already space-optimized at O(n).
Problem: Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. Operations: insert, delete, replace.
function minDistance(word1, word2) {
function dp(i, j) {
if (i === 0) return j; // insert all chars from word2
if (j === 0) return i; // delete all chars from word1
if (word1[i - 1] === word2[j - 1]) {
return dp(i - 1, j - 1);
}
return 1 + Math.min(
dp(i - 1, j), // delete
dp(i, j - 1), // insert
dp(i - 1, j - 1) // replace
);
}
return dp(word1.length, word2.length);
}
// Time: O(3^(m+n)), Space: O(m+n)function minDistance(word1, word2) {
const memo = new Map();
function dp(i, j) {
if (i === 0) return j;
if (j === 0) return i;
const key = `${i},${j}`;
if (memo.has(key)) return memo.get(key);
let result;
if (word1[i - 1] === word2[j - 1]) {
result = dp(i - 1, j - 1);
} else {
result = 1 + Math.min(
dp(i - 1, j),
dp(i, j - 1),
dp(i - 1, j - 1)
);
}
memo.set(key, result);
return result;
}
return dp(word1.length, word2.length);
}
// Time: O(m*n), Space: O(m*n)function minDistance(word1, word2) {
const m = word1.length, n = word2.length;
const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
// Base cases
for (let i = 0; i <= m; i++) dp[i][0] = i;
for (let j = 0; j <= n; j++) dp[0][j] = j;
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + Math.min(
dp[i - 1][j], // delete
dp[i][j - 1], // insert
dp[i - 1][j - 1] // replace
);
}
}
}
return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)function minDistance(word1, word2) {
const m = word1.length, n = word2.length;
let prev = Array(n + 1).fill(0).map((_, j) => j);
for (let i = 1; i <= m; i++) {
const curr = Array(n + 1).fill(0);
curr[0] = i;
for (let j = 1; j <= n; j++) {
if (word1[i - 1] === word2[j - 1]) {
curr[j] = prev[j - 1];
} else {
curr[j] = 1 + Math.min(
prev[j], // delete
curr[j - 1], // insert
prev[j - 1] // replace
);
}
}
prev = curr;
}
return prev[n];
}
// Time: O(m*n), Space: O(n)Problem: Given two strings text1 and text2, return the length of their longest common subsequence.
function longestCommonSubsequence(text1, text2) {
function dp(i, j) {
if (i === 0 || j === 0) return 0;
if (text1[i - 1] === text2[j - 1]) {
return 1 + dp(i - 1, j - 1);
}
return Math.max(dp(i - 1, j), dp(i, j - 1));
}
return dp(text1.length, text2.length);
}
// Time: O(2^(m+n)), Space: O(m+n)function longestCommonSubsequence(text1, text2) {
const memo = new Map();
function dp(i, j) {
if (i === 0 || j === 0) return 0;
const key = `${i},${j}`;
if (memo.has(key)) return memo.get(key);
let result;
if (text1[i - 1] === text2[j - 1]) {
result = 1 + dp(i - 1, j - 1);
} else {
result = Math.max(dp(i - 1, j), dp(i, j - 1));
}
memo.set(key, result);
return result;
}
return dp(text1.length, text2.length);
}
// Time: O(m*n), Space: O(m*n)function longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));
for (let i = 1; i <= m; i++) {
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
dp[i][j] = 1 + dp[i - 1][j - 1];
} else {
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
}
}
}
return dp[m][n];
}
// Time: O(m*n), Space: O(m*n)function longestCommonSubsequence(text1, text2) {
const m = text1.length, n = text2.length;
let prev = Array(n + 1).fill(0);
for (let i = 1; i <= m; i++) {
const curr = Array(n + 1).fill(0);
for (let j = 1; j <= n; j++) {
if (text1[i - 1] === text2[j - 1]) {
curr[j] = 1 + prev[j - 1];
} else {
curr[j] = Math.max(prev[j], curr[j - 1]);
}
}
prev = curr;
}
return prev[n];
}
// Time: O(m*n), Space: O(n)Problem: Given an integer array nums, return the length of the longest strictly increasing subsequence.
function lengthOfLIS(nums) {
function dp(i, prevIdx) {
if (i === nums.length) return 0;
// Option 1: Don't take current element
let notTake = dp(i + 1, prevIdx);
// Option 2: Take current element (if valid)
let take = 0;
if (prevIdx === -1 || nums[i] > nums[prevIdx]) {
take = 1 + dp(i + 1, i);
}
return Math.max(take, notTake);
}
return dp(0, -1);
}
// Time: O(2^n), Space: O(n)function lengthOfLIS(nums) {
const memo = new Map();
function dp(i, prevIdx) {
if (i === nums.length) return 0;
const key = `${i},${prevIdx}`;
if (memo.has(key)) return memo.get(key);
let notTake = dp(i + 1, prevIdx);
let take = 0;
if (prevIdx === -1 || nums[i] > nums[prevIdx]) {
take = 1 + dp(i + 1, i);
}
const result = Math.max(take, notTake);
memo.set(key, result);
return result;
}
return dp(0, -1);
}
// Time: O(n^2), Space: O(n^2)function lengthOfLIS(nums) {
const n = nums.length;
const dp = Array(n).fill(1);
for (let i = 1; i < n; i++) {
for (let j = 0; j < i; j++) {
if (nums[i] > nums[j]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Math.max(...dp);
}
// Time: O(n^2), Space: O(n)function lengthOfLIS(nums) {
const tails = [];
for (const num of nums) {
let left = 0, right = tails.length;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (tails[mid] < num) {
left = mid + 1;
} else {
right = mid;
}
}
if (left === tails.length) {
tails.push(num);
} else {
tails[left] = num;
}
}
return tails.length;
}
// Time: O(n log n), Space: O(n)Problem: Given an array of coins and an amount, return the minimum number of coins needed to make up that amount. Return -1 if impossible.
function coinChange(coins, amount) {
function dp(remaining) {
if (remaining === 0) return 0;
if (remaining < 0) return Infinity;
let minCoins = Infinity;
for (const coin of coins) {
minCoins = Math.min(minCoins, 1 + dp(remaining - coin));
}
return minCoins;
}
const result = dp(amount);
return result === Infinity ? -1 : result;
}
// Time: O(amount^coins), Space: O(amount)function coinChange(coins, amount) {
const memo = new Map();
function dp(remaining) {
if (remaining === 0) return 0;
if (remaining < 0) return Infinity;
if (memo.has(remaining)) return memo.get(remaining);
let minCoins = Infinity;
for (const coin of coins) {
minCoins = Math.min(minCoins, 1 + dp(remaining - coin));
}
memo.set(remaining, minCoins);
return minCoins;
}
const result = dp(amount);
return result === Infinity ? -1 : result;
}
// Time: O(amount * coins), Space: O(amount)function coinChange(coins, amount) {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++) {
for (const coin of coins) {
if (i - coin >= 0) {
dp[i] = Math.min(dp[i], 1 + dp[i - coin]);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}
// Time: O(amount * coins), Space: O(amount)For this problem, the bottom-up solution is already space-optimized at O(amount).
Problem: Given an array of distinct integers nums and a target integer target, return the number of possible combinations that add up to target.
function combinationSum4(nums, target) {
function dp(remaining) {
if (remaining === 0) return 1;
if (remaining < 0) return 0;
let count = 0;
for (const num of nums) {
count += dp(remaining - num);
}
return count;
}
return dp(target);
}
// Time: O(target^nums), Space: O(target)function combinationSum4(nums, target) {
const memo = new Map();
function dp(remaining) {
if (remaining === 0) return 1;
if (remaining < 0) return 0;
if (memo.has(remaining)) return memo.get(remaining);
let count = 0;
for (const num of nums) {
count += dp(remaining - num);
}
memo.set(remaining, count);
return count;
}
return dp(target);
}
// Time: O(target * nums), Space: O(target)function combinationSum4(nums, target) {
const dp = Array(target + 1).fill(0);
dp[0] = 1;
for (let i = 1; i <= target; i++) {
for (const num of nums) {
if (i - num >= 0) {
dp[i] += dp[i - num];
}
}
}
return dp[target];
}
// Time: O(target * nums), Space: O(target)For this problem, the bottom-up solution is already space-optimized at O(target).
Problem: Given a string s containing only digits, return the number of ways to decode it. 'A' -> "1", 'B' -> "2", ..., 'Z' -> "26".
function numDecodings(s) {
function dp(i) {
if (i === s.length) return 1;
if (s[i] === '0') return 0;
// Single digit decode
let ways = dp(i + 1);
// Two digit decode
if (i + 1 < s.length) {
const twoDigit = parseInt(s.slice(i, i + 2));
if (twoDigit <= 26) {
ways += dp(i + 2);
}
}
return ways;
}
return dp(0);
}
// Time: O(2^n), Space: O(n)function numDecodings(s) {
const memo = new Map();
function dp(i) {
if (i === s.length) return 1;
if (s[i] === '0') return 0;
if (memo.has(i)) return memo.get(i);
let ways = dp(i + 1);
if (i + 1 < s.length) {
const twoDigit = parseInt(s.slice(i, i + 2));
if (twoDigit <= 26) {
ways += dp(i + 2);
}
}
memo.set(i, ways);
return ways;
}
return dp(0);
}
// Time: O(n), Space: O(n)function numDecodings(s) {
const n = s.length;
const dp = Array(n + 1).fill(0);
dp[n] = 1; // empty string
for (let i = n - 1; i >= 0; i--) {
if (s[i] === '0') {
dp[i] = 0;
} else {
dp[i] = dp[i + 1];
if (i + 1 < n) {
const twoDigit = parseInt(s.slice(i, i + 2));
if (twoDigit <= 26) {
dp[i] += dp[i + 2];
}
}
}
}
return dp[0];
}
// Time: O(n), Space: O(n)function numDecodings(s) {
const n = s.length;
let next1 = 1; // dp[i+1]
let next2 = 0; // dp[i+2]
for (let i = n - 1; i >= 0; i--) {
let current = 0;
if (s[i] !== '0') {
current = next1;
if (i + 1 < n) {
const twoDigit = parseInt(s.slice(i, i + 2));
if (twoDigit <= 26) {
current += next2;
}
}
}
next2 = next1;
next1 = current;
}
return next1;
}
// Time: O(n), Space: O(1)Problem: You have planned some train traveling for the next year. Days you will travel is given as days array. Train tickets are sold in 1-day, 7-day, and 30-day passes with costs costs[0], costs[1], costs[2]. Return minimum cost.
function mincostTickets(days, costs) {
const daySet = new Set(days);
function dp(day) {
if (day > days[days.length - 1]) return 0;
if (!daySet.has(day)) {
return dp(day + 1);
}
return Math.min(
costs[0] + dp(day + 1),
costs[1] + dp(day + 7),
costs[2] + dp(day + 30)
);
}
return dp(days[0]);
}
// Time: O(3^n), Space: O(n)function mincostTickets(days, costs) {
const daySet = new Set(days);
const memo = new Map();
function dp(day) {
if (day > days[days.length - 1]) return 0;
if (memo.has(day)) return memo.get(day);
let result;
if (!daySet.has(day)) {
result = dp(day + 1);
} else {
result = Math.min(
costs[0] + dp(day + 1),
costs[1] + dp(day + 7),
costs[2] + dp(day + 30)
);
}
memo.set(day, result);
return result;
}
return dp(days[0]);
}
// Time: O(max_day), Space: O(max_day)function mincostTickets(days, costs) {
const lastDay = days[days.length - 1];
const daySet = new Set(days);
const dp = Array(lastDay + 1).fill(0);
for (let day = 1; day <= lastDay; day++) {
if (!daySet.has(day)) {
dp[day] = dp[day - 1];
} else {
dp[day] = Math.min(
dp[day - 1] + costs[0],
dp[Math.max(0, day - 7)] + costs[1],
dp[Math.max(0, day - 30)] + costs[2]
);
}
}
return dp[lastDay];
}
// Time: O(max_day), Space: O(max_day)function mincostTickets(days, costs) {
const queue7 = []; // [day, cost]
const queue30 = [];
let cost = 0;
for (const day of days) {
// Remove expired 7-day passes
while (queue7.length && queue7[0][0] + 7 <= day) {
queue7.shift();
}
// Remove expired 30-day passes
while (queue30.length && queue30[0][0] + 30 <= day) {
queue30.shift();
}
queue7.push([day, cost + costs[1]]);
queue30.push([day, cost + costs[2]]);
cost = Math.min(
cost + costs[0],
queue7[0][1],
queue30[0][1]
);
}
return cost;
}
// Time: O(n), Space: O(38) = O(1)- Climbing Stairs, House Robber
- Key: Current state depends on previous 1-2 states
- Space Optimization: Keep only last 2 values
- Unique Paths, Minimum Path Sum
- Key: Build solution row by row or cell by cell
- Space Optimization: Keep only previous row
- Word Break, Decode Ways, Edit Distance
- Key: Build solution character by character
- Space Optimization: Often already O(n)
- LIS, LCS
- Key: Include/exclude current element
- LIS Optimization: Binary search approach
- Coin Change, Combination Sum
- Key: Unbounded - can use items multiple times
- Space Optimization: 1D array sufficient
- Look for optimal substructure
- Check for overlapping subproblems
- Keywords: "minimum", "maximum", "count ways", "longest"
- Start with recursive solution (understand the problem)
- Add memoization (top-down)
- Convert to tabulation (bottom-up)
- Optimize space (if needed)
- Off-by-one errors in indices
- Wrong base cases
- Not handling edge cases (empty input, single element)
- Forgetting to check bounds in 2D problems
- Spend 5 min understanding the problem
- Write recursive solution first (even if inefficient)
- Explain optimization approach before coding
- Test with examples
- Explain your thought process
- Discuss trade-offs (time vs space)
- Mention alternative approaches
- Always analyze complexity