DSA for Interviews, From Zero

Part 14 · Lesson 56 · read

2-D Dynamic Programming

Paths on a grid and the 0/1 knapsack problems.

On this page

  1. When one index is not enough
  2. Grid paths
  3. Paths with obstacles
  4. Minimum path sum
  5. Traced: minimum path sum
  6. 0/1 knapsack
  7. One row, capacity going downwards
  8. Partition equal subset sum
  9. Unbounded knapsack: coin change II
  10. Loop order: combinations vs permutations
  11. Practice questions (7)
  12. Make it stick
  13. What's next

When one index is not enough

Lesson 55 saved one answer for each index. Some problems need two numbers to describe a small part of the problem (a subproblem is a smaller version of the same question; solving all of them solves the big one). For example, a row and a column on a board. Or “how many items have I looked at” and “how much room is left in the bag”. Then the table is 2-D (two-dimensional, like a spreadsheet with rows and columns). Each cell dp[i][j] answers one small question for one pair of numbers. The recipe is the same as before. First say in words what dp[i][j] means. Then set the starting values (the base cases). Then write the rule (the transition) that uses the last choice you made. Last, fill the table in an order where each answer is ready before you need it.

Grid paths

A robot starts at the top-left of a grid. It can only move right or down. How many different routes reach the bottom-right? The meaning of one cell (the “state”) is: dp[r][c] = the number of ways to reach cell (r, c). The robot came into that cell from above or from the left. Those are different routes, so we add the two counts. The top row and the left column have exactly one way each (straight along the edge).

JavaScript
// State: dp[r][c] = the number of ways to reach cell (r, c) moving only right or down.function uniquePaths(rows, cols) {  const dp = Array.from({ length: rows }, () => new Array(cols).fill(1));  // first row and column: exactly 1 way  for (let r = 1; r < rows; r++) {    for (let c = 1; c < cols; c++) {      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];   // arrive from above, or from the left    }  }  return dp[rows - 1][cols - 1];}console.log(uniquePaths(3, 3)); // 6console.log(uniquePaths(3, 7)); // 28

Time and memory are both O(rows × cols). Each cell is worked out once, using its two neighbours.

Paths with obstacles

Now some cells are blocked (marked 1). The idea stays the same. A blocked cell has 0 ways to be reached, so it adds 0 to the cells after it. Watch the edges. A blocked cell in the first row cuts off everything after it in that row. The formula does this by itself, so you need no extra code.

JavaScript
// Same state, but an obstacle cell has 0 ways to be reached.function uniquePathsWithObstacles(grid) {  const rows = grid.length, cols = grid[0].length;  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));  for (let r = 0; r < rows; r++) {    for (let c = 0; c < cols; c++) {      if (grid[r][c] === 1) { dp[r][c] = 0; continue; }       // blocked      if (r === 0 && c === 0) { dp[r][c] = 1; continue; }     // the start      const above = r > 0 ? dp[r - 1][c] : 0;      const left = c > 0 ? dp[r][c - 1] : 0;      dp[r][c] = above + left;    }  }  return dp[rows - 1][cols - 1];}console.log(uniquePathsWithObstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]])); // 2console.log(uniquePathsWithObstacles([[0, 1], [0, 0]]));                  // 1
Blocked start
If the start cell is blocked, the answer is 0. The code above handles this because it checks for an obstacle first.

Minimum path sum

Each cell has a cost. Find the right-and-down route with the smallest total. The moves are the same, but now we find thesmallest value instead of counting: dp[r][c] = the smallest total cost of a route from the top-left to (r, c). Pay for the cell itself, plus the cheaper of the two ways in. A cell on an edge has only one way in. So we treat the missing neighbour as Infinity (a number bigger than any other), because it can never be the smallest.

JavaScript
// State: dp[r][c] = the smallest sum of a path from the top-left to (r, c).function minPathSum(grid) {  const rows = grid.length, cols = grid[0].length;  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));  dp[0][0] = grid[0][0];  for (let r = 0; r < rows; r++) {    for (let c = 0; c < cols; c++) {      if (r === 0 && c === 0) continue;      const fromAbove = r > 0 ? dp[r - 1][c] : Infinity;   // off the grid = not an option      const fromLeft = c > 0 ? dp[r][c - 1] : Infinity;      dp[r][c] = grid[r][c] + Math.min(fromAbove, fromLeft);    }  }  return dp[rows - 1][cols - 1];}console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])); // 7

Traced: minimum path sum

step 1 / 12
Set up
a 3 by 3 grid

Each cell has a cost. We want the cheapest route from the top-left to the bottom-right. We can only move right or down.

▶const rows = grid.length, cols = grid[0].length;2const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));3dp[0][0] = grid[0][0];4for (let r = 0; r < rows; r++) {5  for (let c = 0; c < cols; c++) {6    if (r === 0 && c === 0) continue;7    const fromAbove = r > 0 ? dp[r - 1][c] : Infinity;8    const fromLeft = c > 0 ? dp[r][c - 1] : Infinity;9    dp[r][c] = grid[r][c] + Math.min(fromAbove, fromLeft);10  }11}12return dp[rows - 1][cols - 1];
Variables
grid[[1, 3, 1], [1, 5, 1], [4, 2, 1]]
rows3
cols3
Console
(nothing printed yet)
The table fills row by row. Look at dp[1][1]. The cell costs 5 and the cheaper way in costs 2, so it is 7. The final route reaches the corner through dp[1][2] = 6, so it avoids that expensive middle cell. · interactive

0/1 knapsack

You have some items. Each item has a weight and a value. You also have a bag that can hold a total weight of at most capacity. Pick items to get the biggest total value. “0/1” means you take each item once, or not at all. Think of packing a suitcase for a trip: each thing goes in once, and the case has a weight limit. The opposite, “unbounded” knapsack, lets you take the same item many times (see below).

State: dp[i][w] = the best total value when you use only the first i items and the bag holds weight w. For item i you make one yes-or-no choice. Skip it: the answer is dp[i-1][w]. Take it (only if it fits): you gain its value, and you have w - weight room left for the earlier items. That gives dp[i-1][w - weight] + value. Keep the larger of the two.

JavaScript
// 0/1 knapsack: each item is used at most once.// State: dp[i][w] = the best total value using only the first i items with capacity w.function knapsack(weights, values, capacity) {  const n = weights.length;  const dp = Array.from({ length: n + 1 }, () => new Array(capacity + 1).fill(0));  // row 0: no items, value 0  for (let i = 1; i <= n; i++) {    for (let w = 0; w <= capacity; w++) {      dp[i][w] = dp[i - 1][w];                              // skip item i      if (weights[i - 1] <= w) {                            // or take it, if it fits        dp[i][w] = Math.max(dp[i][w], dp[i - 1][w - weights[i - 1]] + values[i - 1]);      }    }  }  return dp[n][capacity];}console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9   (the items of weight 3 and 4)

This takes O(n × capacity) time and memory.

One row, capacity downwards

Row i only reads row i - 1. So one array is enough. After we process item i, dp[w] holds what row i would have held. Memory drops to O(capacity). But there is one trap: the capacity loop must go from high to low.

JavaScript
// Row i only reads row i - 1, so one array is enough, IF capacity runs downwards.function knapsack(weights, values, capacity) {  const dp = new Array(capacity + 1).fill(0);  for (let i = 0; i < weights.length; i++) {    for (let w = capacity; w >= weights[i]; w--) {          // high to low      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);    }  }  return dp[capacity];}console.log(knapsack([1, 3, 4, 5], [1, 4, 5, 7], 7)); // 9
Dry run · weights [1, 3, 4, 5], values [1, 4, 5, 7], capacity 7
AfterItemdp[0..7]
start-[0, 0, 0, 0, 0, 0, 0, 0]
item 1weight 1, value 1[0, 1, 1, 1, 1, 1, 1, 1]
item 2weight 3, value 4[0, 1, 1, 4, 5, 5, 5, 5]
item 3weight 4, value 5[0, 1, 1, 4, 5, 6, 6, 9]
item 4weight 5, value 7[0, 1, 1, 4, 5, 7, 8, 9]

The last number is the answer, 9. It comes from the items with weight 3 and weight 4 (value 4 + 5).

Why downwards? The update for dp[w] reads dp[w - weight], which is a smaller index. When we go from high to low, that smaller cell has not changed yet for this item. It still holds the answer from before this item, so the item is added at most once. When we go from low to high, the smaller cell was already updated for this item. It may already include the item, so we add the item again. The loop then allows unlimited copies, and nothing warns you:

JavaScript
// The same loop with capacity going UP: this no longer means 'each item once'.function ascending(weights, values, capacity) {  const dp = new Array(capacity + 1).fill(0);  for (let i = 0; i < weights.length; i++) {    for (let w = weights[i]; w <= capacity; w++) {          // low to high      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);    }  }  return dp[capacity];}// One item, weight 2 and value 3, capacity 6. Correct answer: 3 (we own just one).console.log(ascending([2], [3], 6)); // 9   the item was counted three times

Partition equal subset sum

Can an array of positive whole numbers be split into two groups with equal sums? If the total is odd, the answer is no. Otherwise we need a subset (some of the numbers) that adds up to exactly half the total. The numbers left over then make the other half. This is knapsack in disguise. The weights are the numbers, the capacity is the target, and the question is yes or no: “can we hit the target exactly?” State: dp[s] = true if some subset of the numbers seen so far adds up to exactly s. Each number is used once, so the loop runs downwards.

JavaScript
// Can the numbers be split into two groups with equal sums?// That is: is there a subset that adds up to exactly half the total?function canPartition(nums) {  const total = nums.reduce((a, b) => a + b, 0);  if (total % 2 !== 0) return false;        // an odd total cannot be split evenly  const target = total / 2;  const dp = new Array(target + 1).fill(false);   // dp[s] = can some chosen subset sum to exactly s?  dp[0] = true;                             // the empty subset sums to 0  for (const x of nums) {    for (let s = target; s >= x; s--) {     // downwards: each number used at most once      if (dp[s - x]) dp[s] = true;    }  }  return dp[target];}console.log(canPartition([1, 5, 11, 5])); // true   (11 and 1 + 5 + 5)console.log(canPartition([1, 2, 3, 5]));  // false

Unbounded knapsack: coin change II

Unbounded means you can use each item as many times as you like. Coin change II asks this. You have unlimited coins of given values. In how many different combinations can you make the amount? (The same coins in a different order count as one answer.) The one-row loop here is the one that looked like a bug a moment ago. Capacity now runs upwards. Reading a cell that already includes the current coin is exactly what lets us use the coin again.

JavaScript
// Coin change II: the number of COMBINATIONS of coins that make the amount (each coin reusable).// State: dp[a] = the number of ways to make amount a using the coin types processed so far.function change(amount, coins) {  const dp = new Array(amount + 1).fill(0);  dp[0] = 1;                                // one way to make 0: take nothing  for (const coin of coins) {               // coins on the OUTSIDE    for (let a = coin; a <= amount; a++) {  // upwards: the same coin may be used again      dp[a] += dp[a - coin];    }  }  return dp[amount];}console.log(change(5, [1, 2, 5])); // 4   (5, 2+2+1, 2+1+1+1, 1+1+1+1+1)console.log(change(3, [2]));       // 0

Loop order: combinations vs permutations

Put the coins on the outside. We decide how many of coin 1 to use, then coin 2, and so on. Every way is built in one fixed coin order. So 1 + 2 and 2 + 1 cannot both appear. You are counting combinations (order does not matter). Now put the amount on the outside and the coins inside. At each amount, any coin can be the last one added. So different orders of the same coins are counted separately. These are permutations (order matters). This is the question “Combination Sum IV”. The rule is the same, only the loops are swapped, and so the question changes.

JavaScript
// Swap the loops (amount outside, coins inside) and the count changes meaning.function countOrderedWays(amount, coins) {  const dp = new Array(amount + 1).fill(0);  dp[0] = 1;  for (let a = 1; a <= amount; a++) {       // amount on the OUTSIDE    for (const coin of coins) {      if (coin <= a) dp[a] += dp[a - coin];    }  }  return dp[amount];}console.log(countOrderedWays(3, [1, 2])); // 3   (1+1+1, 1+2 and 2+1 all count)
Dry run · amount 3, coins [1, 2]: the table dp[0..3]
Loop orderStartAfter coin 1 / amount 1After coin 2 / amounts 2 and 3Answer
coins outside, amounts inside (change)[1, 0, 0, 0][1, 1, 1, 1][1, 1, 2, 2]2 (1+1+1, 1+2)
amounts outside, coins inside[1, 0, 0, 0]dp[1] = dp[0] = 1dp[2] = dp[1] + dp[0] = 2, dp[3] = dp[2] + dp[1] = 33 (1+1+1, 1+2, 2+1)

Combinations: 1+1+1 and 1+2. Permutations also count 2+1 as a separate answer.

Practice questions

Before you write code, say what dp[i][j] means. Also say which direction each loop should run, and why.

Q1Unique pathsMedium

A robot stands in the top-left of an m × n grid. It can only move right or down. Return the number of different routes to the bottom-right corner.

Example 1
Input: m = 3, n = 7
Output: 28
Explanation: A 3 by 7 grid has 28 different right-or-down routes to the far corner.
Example 2
Input: m = 3, n = 2
Output: 3
Explanation: Right-down-down, down-right-down and down-down-right.
Example 3
Input: m = 1, n = 1
Output: 1
Explanation: You are already at the goal, so there is one (empty) route.
Stuck? Open one hint at a time
Hint 1
State: dp[r][c] is the number of ways to reach cell (r, c).
Hint 2
The last move came from above or from the left. Do you add the two counts, or pick one?
Hint 3
Each row only needs the row above it. Could one array be enough?
Show all 3 solutions with explanations
Approach 12-D table
The idea

Fill the first row and the first column with 1 (there is one straight route). Then use dp[r][c] = dp[r-1][c] + dp[r][c-1].

JavaScript
function uniquePaths(m, n) {  const dp = Array.from({ length: m }, () => new Array(n).fill(1));  for (let r = 1; r < m; r++) {    for (let c = 1; c < n; c++) {      dp[r][c] = dp[r - 1][c] + dp[r][c - 1];    }  }  return dp[m - 1][n - 1];}console.log(uniquePaths(3, 7)); // 28console.log(uniquePaths(3, 2)); // 3console.log(uniquePaths(1, 1)); // 1
How it works

O(m × n) time and memory. Each cell is worked out from two neighbours that are already filled.

Approach 2One row
The idea

Keep one array dp for the current row. Before the update, dp[c] is the cell above. dp[c - 1] is already the cell to the left.

JavaScript
function uniquePaths(m, n) {  const dp = new Array(n).fill(1);  for (let r = 1; r < m; r++) {    for (let c = 1; c < n; c++) {      dp[c] += dp[c - 1];            // above (old dp[c]) + left (new dp[c - 1])    }  }  return dp[n - 1];}console.log(uniquePaths(3, 7)); // 28console.log(uniquePaths(3, 2)); // 3console.log(uniquePaths(1, 1)); // 1
How it works

O(m × n) time, O(n) memory. Going left to right is correct here, because we want the left cell to be already updated for this row.

Approach 3Counting with a formula
The idea

Every route has exactly m - 1 down moves and n - 1 right moves. A route is just a choice of which of the m + n - 2 moves are the down ones. The answer is C(m + n - 2, m - 1). C(a, b) is called a binomial coefficient. It means “the number of ways to choose b things from a things when the order does not matter”.

JavaScript
function uniquePaths(m, n) {  const total = m + n - 2;  const k = Math.min(m, n) - 1;  let result = 1;  for (let i = 1; i <= k; i++) {    result = (result * (total - k + i)) / i;   // this is always a whole number  }  return Math.round(result);}console.log(uniquePaths(3, 7)); // 28console.log(uniquePaths(3, 2)); // 3console.log(uniquePaths(1, 1)); // 1
How it works

O(min(m, n)) time, O(1) memory. It is a nice shortcut here. But it stops working as soon as there are obstacles, so the DP is worth knowing.

Which approach should you use?

Learn the table, because the same shape solves the obstacle and cost versions. The formula is a good way to check your answer. (LeetCode 62.)

Q2Unique paths IIMedium

This is the same robot and grid as the last question, but some cells hold an obstacle (1; free cells are 0). The robot cannot enter an obstacle. Return the number of routes to the bottom-right corner.

Example 1
Input: obstacleGrid = [[0,0,0],[0,1,0],[0,0,0]]
Output: 2
Explanation: The centre is blocked. Both routes go around it: right-right-down-down and down-down-right-right.
Example 2
Input: obstacleGrid = [[0,1],[0,0]]
Output: 1
Explanation: Only down then right works.
Example 3
Input: obstacleGrid = [[1,0]]
Output: 0
Explanation: The start itself is blocked.
Stuck? Open one hint at a time
Hint 1
The state is the same as before. How many ways are there to reach a blocked cell?
Hint 2
Check for an obstacle first, before you add the neighbours.
Hint 3
The start cell is special. It has one way if it is open.
Show all 2 solutions with explanations
Approach 12-D table
The idea

Obstacle cell: 0. Start cell: 1. Any other cell: the cell above plus the cell to the left. A place off the grid counts as 0.

JavaScript
function uniquePathsWithObstacles(grid) {  const rows = grid.length, cols = grid[0].length;  const dp = Array.from({ length: rows }, () => new Array(cols).fill(0));  for (let r = 0; r < rows; r++) {    for (let c = 0; c < cols; c++) {      if (grid[r][c] === 1) continue;                  // stays 0      if (r === 0 && c === 0) { dp[r][c] = 1; continue; }      dp[r][c] = (r > 0 ? dp[r - 1][c] : 0) + (c > 0 ? dp[r][c - 1] : 0);    }  }  return dp[rows - 1][cols - 1];}console.log(uniquePathsWithObstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]])); // 2console.log(uniquePathsWithObstacles([[0, 1], [0, 0]]));                  // 1console.log(uniquePathsWithObstacles([[1, 0]]));                          // 0
How it works

O(rows × cols) time and memory. If the start is blocked, every cell stays 0, so the answer is 0.

Approach 2One row
The idea

Start with dp = [1, 0, 0, ...], which says “one way to be just above the first cell”. For every cell: if it is blocked, set it to 0. Otherwise add the cell on the left.

JavaScript
function uniquePathsWithObstacles(grid) {  const cols = grid[0].length;  const dp = new Array(cols).fill(0);  dp[0] = 1;  for (const row of grid) {    for (let c = 0; c < cols; c++) {      if (row[c] === 1) dp[c] = 0;            // blocked: nothing reaches it      else if (c > 0) dp[c] += dp[c - 1];     // above (kept in dp[c]) + left    }  }  return dp[cols - 1];}console.log(uniquePathsWithObstacles([[0, 0, 0], [0, 1, 0], [0, 0, 0]])); // 2console.log(uniquePathsWithObstacles([[0, 1], [0, 0]]));                  // 1console.log(uniquePathsWithObstacles([[1, 0]]));                          // 0
How it works

O(rows × cols) time, O(cols) memory. The first column keeps its value from the row above until an obstacle sets it to 0.

Which approach should you use?

The table is easier to get right. The single row is the follow-up question. (LeetCode 63.)

Q3Minimum path sumMedium

Given a grid of numbers that are zero or more, find a route from the top-left to the bottom-right (moving only right or down) with the smallest total of cell values. Return that total.

Example 1
Input: grid = [[1,3,1],[1,5,1],[4,2,1]]
Output: 7
Explanation: Route 1 → 3 → 1 → 1 → 1 sums to 7.
Example 2
Input: grid = [[1,2,3],[4,5,6]]
Output: 12
Explanation: Route 1 → 2 → 3 → 6 sums to 12.
Stuck? Open one hint at a time
Hint 1
State: dp[r][c] is the lowest cost to arrive at (r, c).
Hint 2
You pay for the cell, plus the cheaper of the two ways in.
Hint 3
On the first row and column there is only one way in. Treat a missing neighbour as Infinity (a number bigger than any other).
Show all 2 solutions with explanations
Approach 1Recursion with memo
The idea

best(r, c) is the lowest cost from (r, c) to the end: the cell plus the cheaper of going down or going right. A memo (memoization) means saving each answer after you work it out, so you never work it out twice. We save the answer for each cell. Without it, the code would walk every route one by one.

JavaScript
function minPathSum(grid) {  const rows = grid.length, cols = grid[0].length;  const memo = new Map();  function best(r, c) {    if (r === rows - 1 && c === cols - 1) return grid[r][c];    const key = r * cols + c;    if (memo.has(key)) return memo.get(key);    const down = r + 1 < rows ? best(r + 1, c) : Infinity;    const right = c + 1 < cols ? best(r, c + 1) : Infinity;    const result = grid[r][c] + Math.min(down, right);    memo.set(key, result);    return result;  }  return best(0, 0);}console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])); // 7console.log(minPathSum([[1, 2, 3], [4, 5, 6]]));            // 12
How it works

One saved answer per cell, so O(rows × cols) time and memory. The call depth is rows + cols. Without the memo, the number of calls grows as fast as the number of routes. That is exponential, which means it doubles again and again.

Approach 2One row, bottom-up
The idea

Walk the grid in reading order (left to right, top to bottom) and keep one array. Before the update, dp[c] is the cost from above. dp[c - 1] is the cost from the left.

JavaScript
function minPathSum(grid) {  const rows = grid.length, cols = grid[0].length;  const dp = new Array(cols).fill(Infinity);  dp[0] = 0;                                   // so the start cell costs only itself  for (let r = 0; r < rows; r++) {    for (let c = 0; c < cols; c++) {      const fromLeft = c > 0 ? dp[c - 1] : Infinity;      dp[c] = grid[r][c] + Math.min(dp[c], fromLeft);    }  }  return dp[cols - 1];}console.log(minPathSum([[1, 3, 1], [1, 5, 1], [4, 2, 1]])); // 7console.log(minPathSum([[1, 2, 3], [4, 5, 6]]));            // 12
How it works

O(rows × cols) time, O(cols) memory. On the first row, dp[c] is still Infinity, so only the left neighbour counts. In the first column there is no left neighbour, so only the cell above counts.

Which approach should you use?

Start with the memo, because it follows how you think. Use the row version when memory matters. A greedy method (a method that always takes the choice that looks best right now) fails here (“always pick the cheaper next step”), because a cheap step can lead into expensive cells. (LeetCode 64.)

Q4Partition equal subset sumMedium

Given an array of positive whole numbers, return true if it can be split into two subsets (groups) with equal sums.

Example 1
Input: nums = [1,5,11,5]
Output: true
Explanation: [1,5,5] and [11] both sum to 11.
Example 2
Input: nums = [1,2,3,5]
Output: false
Explanation: The total is 11, which is odd, so no even split exists.
Stuck? Open one hint at a time
Hint 1
If the total is odd, stop. Otherwise, what sum must one subset reach?
Hint 2
It is a knapsack problem. The items are the numbers, and you ask if you can hit the target exactly.
Hint 3
Each number is used once. Which direction should the sum loop go?
Show all 2 solutions with explanations
Approach 1Recursion with memo
The idea

can(i, rest) asks: do some numbers from index i onward add up to rest? Take nums[i] or skip it. Save each answer by (i, rest).

JavaScript
function canPartition(nums) {  const total = nums.reduce((a, b) => a + b, 0);  if (total % 2 !== 0) return false;  const memo = new Map();  function can(i, rest) {    if (rest === 0) return true;    if (i === nums.length || rest < 0) return false;    const key = i * (total + 1) + rest;    if (memo.has(key)) return memo.get(key);    const result = can(i + 1, rest - nums[i]) || can(i + 1, rest);    memo.set(key, result);    return result;  }  return can(0, total / 2);}console.log(canPartition([1, 5, 11, 5])); // trueconsole.log(canPartition([1, 2, 3, 5]));  // false
How it works

There are at most n × target different states, so O(n × target) time and memory. Without the memo it tries up to 2n subsets.

Approach 21-D true/false table, sums going downwards
The idea

dp[s] is true when some subset adds up to s. For each number x, go through s from high to low and set dp[s] = dp[s] || dp[s - x].

JavaScript
function canPartition(nums) {  const total = nums.reduce((a, b) => a + b, 0);  if (total % 2 !== 0) return false;  const target = total / 2;  const dp = new Array(target + 1).fill(false);  dp[0] = true;  for (const x of nums) {    for (let s = target; s >= x; s--) {      if (dp[s - x]) dp[s] = true;    }  }  return dp[target];}console.log(canPartition([1, 5, 11, 5])); // trueconsole.log(canPartition([1, 2, 3, 5]));  // false
How it works

O(n × target) time, O(target) memory. We go downwards, so each number joins a subset at most once. Going upwards would let a number be used again. For [2, 6] (target 4) it would wrongly say true by using the 2 twice.

Which approach should you use?

Use the 1-D table. The memo is a good first step, because it shows the take-or-skip idea. (LeetCode 416.)

Q5Coin change IIMedium

Given coin values (you have unlimited coins of each) and a target amount, return the number of different combinations of coins that make exactly that amount. Return 0 if it is impossible.

Example 1
Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: 5; 2+2+1; 2+1+1+1; 1+1+1+1+1.
Example 2
Input: amount = 3, coins = [2]
Output: 0
Explanation: Two cannot add up to three.
Example 3
Input: amount = 10, coins = [10]
Output: 1
Explanation: A single 10.
Stuck? Open one hint at a time
Hint 1
Count combinations. 2+1 and 1+2 are the same answer.
Hint 2
State: dp[a] is the number of ways to make a using the coin types handled so far. What should dp[0] be?
Hint 3
Which loop goes on the outside, coins or amounts? Which direction should the amount loop go?
Show all 2 solutions with explanations
Approach 12-D table (coin types × amount)
The idea

dp[i][a] is the number of combinations that make a using only the first i coin types. Either do not use coin i at all (dp[i-1][a]), or use it at least once (dp[i][a - coin], in the same row, because the coin can be used again).

JavaScript
function change(amount, coins) {  const n = coins.length;  const dp = Array.from({ length: n + 1 }, () => new Array(amount + 1).fill(0));  for (let i = 0; i <= n; i++) dp[i][0] = 1;       // one way to make 0 with any coins: take nothing  for (let i = 1; i <= n; i++) {    const coin = coins[i - 1];    for (let a = 1; a <= amount; a++) {      dp[i][a] = dp[i - 1][a] + (a >= coin ? dp[i][a - coin] : 0);    }  }  return dp[n][amount];}console.log(change(5, [1, 2, 5]));  // 4console.log(change(3, [2]));        // 0console.log(change(10, [10]));      // 1
How it works

O(n × amount) time and memory. Notice that the second term reads the same row i. That is how “use this coin as often as you like” looks in a table.

Approach 21-D, coins outside, amounts going upwards
The idea

Squash the rows into one array. With coins on the outside, each combination is built in one fixed coin order, so it is counted once. Amounts going upwards lets a coin be used again.

JavaScript
function change(amount, coins) {  const dp = new Array(amount + 1).fill(0);  dp[0] = 1;  for (const coin of coins) {    for (let a = coin; a <= amount; a++) {      dp[a] += dp[a - coin];    }  }  return dp[amount];}console.log(change(5, [1, 2, 5]));  // 4console.log(change(3, [2]));        // 0console.log(change(10, [10]));      // 1
How it works

O(n × amount) time, O(amount) memory. If you swap the two loops, you count ordered sequences (permutations). Then amount 3 with coins [1, 2] gives 3 instead of 2.

Which approach should you use?

Write the 1-D version, and be ready to explain the loop order. Interviewers often ask exactly this: combinations or permutations. (LeetCode 518.)

Q6Target sumMedium

Given an array of whole numbers (zero or more) and a target, put a + or - in front of every number. Return how many ways of choosing the signs make the result equal target.

Example 1
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: Choose which one of the 1s gets a minus sign: -1+1+1+1+1 and four others. That is five ways to total 3.
Example 2
Input: nums = [1], target = 1
Output: 1
Explanation: +1.
Stuck? Open one hint at a time
Hint 1
Every number gets a plus or a minus. Trying every choice (brute force) means 2n options.
Hint 2
Describe each situation as (index, running sum). Then identical situations can share one saved answer.
Hint 3
Call the group with plus signs P and the group with minus signs N. Then P + N = total and P − N = target. What is P?
Show all 2 solutions with explanations
Approach 1Recursion with memo
The idea

ways(i, sum) counts the sign choices for the numbers from i onward that make the running sum reach the target. Try +nums[i] and -nums[i]. Save each answer by (i, sum).

JavaScript
function findTargetSumWays(nums, target) {  const memo = new Map();  function ways(i, sum) {    if (i === nums.length) return sum === target ? 1 : 0;    const key = i + "," + sum;    if (memo.has(key)) return memo.get(key);    const result = ways(i + 1, sum + nums[i]) + ways(i + 1, sum - nums[i]);    memo.set(key, result);    return result;  }  return ways(0, 0);}console.log(findTargetSumWays([1, 1, 1, 1, 1], 3)); // 5console.log(findTargetSumWays([1], 1));             // 1
How it works

The running sum stays between -total and +total, so there are at most n × (2 × total + 1) states. Without the memo it can try 2n paths.

Approach 2Turn it into counting subsets
The idea

Let P be the sum of the numbers with a plus sign, and N the sum of the numbers with a minus sign. Then P + N = total and P − N = target, so P = (total + target) / 2. Now count the subsets that add up to P, using a 0/1 knapsack that counts. If total + target is odd, or |target| > total, the answer is 0.

JavaScript
function findTargetSumWays(nums, target) {  const total = nums.reduce((a, b) => a + b, 0);  if (Math.abs(target) > total || (total + target) % 2 !== 0) return 0;  const want = (total + target) / 2;  const dp = new Array(want + 1).fill(0);  dp[0] = 1;  for (const x of nums) {    for (let s = want; s >= x; s--) {      // downwards: each number is used once      dp[s] += dp[s - x];    }  }  return dp[want];}console.log(findTargetSumWays([1, 1, 1, 1, 1], 3)); // 5console.log(findTargetSumWays([1], 1));             // 1
How it works

In the first example total = 5, so P = (5 + 3) / 2 = 4. There are 5 ways to choose four of the five ones. This takes O(n × P) time and O(P) memory. Zeros in the input work correctly: a 0 doubles the counts, because it can take either sign.

Which approach should you use?

The subset-sum version is shorter and uses less memory. The memo is easier to think of first. Both are fine. (LeetCode 494.)

Q7Maximal squareMedium

Given a grid (matrix) of the characters "0" and "1", find the largest square made only of "1"s and return its area.

Example 1
Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 4
Explanation: The largest square made only of 1s is 2 × 2 (for example rows 1-2, columns 2-3). Its area is 4.
Example 2
Input: matrix = [["0","1"],["1","0"]]
Output: 1
Explanation: No 1s form a bigger square, so the best is a single cell. The area is 1.
Example 3
Input: matrix = [["0"]]
Output: 0
Explanation: No 1s at all.
Stuck? Open one hint at a time
Hint 1
Return the area (side × side), not the side length.
Hint 2
State: dp[r][c] is the side length of the biggest square of 1s whose bottom-right corner is (r, c).
Hint 3
A square with side k at (r, c) needs squares with side k − 1 ending at the cell above, the cell to the left, and the cell diagonally up-left.
Show all 2 solutions with explanations
Approach 1Brute force
The idea

Treat every cell as a top-left corner. Grow the square one size at a time, as long as the new bottom row and new right column are all 1s.

JavaScript
function maximalSquare(matrix) {  const rows = matrix.length, cols = matrix[0].length;  let best = 0;  for (let r = 0; r < rows; r++) {    for (let c = 0; c < cols; c++) {      if (matrix[r][c] !== "1") continue;      let side = 1;      while (r + side < rows && c + side < cols) {        let ok = true;        for (let k = 0; k <= side; k++) {              // the new row and the new column          if (matrix[r + side][c + k] !== "1" || matrix[r + k][c + side] !== "1") { ok = false; break; }        }        if (!ok) break;        side++;      }      best = Math.max(best, side);    }  }  return best * best;}console.log(maximalSquare([["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]])); // 4console.log(maximalSquare([["0", "1"], ["1", "0"]])); // 1console.log(maximalSquare([["0"]]));                  // 0
How it works

O(rows × cols × min(rows, cols)²) in the worst case. Each corner may grow to the full size and re-check a row and a column at each step. This is fine for small grids but too slow for big ones.

Approach 2DP using the bottom-right corner
The idea

If the cell is "1", then dp[r][c] = 1 + min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1]). Otherwise it is 0. The smallest of the three neighbours limits how big the square can be. Add one extra row and column of zeros, so the edges need no special case.

JavaScript
function maximalSquare(matrix) {  const rows = matrix.length, cols = matrix[0].length;  const dp = Array.from({ length: rows + 1 }, () => new Array(cols + 1).fill(0));   // extra row and column of zeros  let side = 0;  for (let r = 1; r <= rows; r++) {    for (let c = 1; c <= cols; c++) {      if (matrix[r - 1][c - 1] === "1") {        dp[r][c] = 1 + Math.min(dp[r - 1][c], dp[r][c - 1], dp[r - 1][c - 1]);        side = Math.max(side, dp[r][c]);      }    }  }  return side * side;}console.log(maximalSquare([["1", "0", "1", "0", "0"], ["1", "0", "1", "1", "1"], ["1", "1", "1", "1", "1"], ["1", "0", "0", "1", "0"]])); // 4console.log(maximalSquare([["0", "1"], ["1", "0"]])); // 1console.log(maximalSquare([["0"]]));                  // 0
How it works

O(rows × cols) time and memory. You can shrink the memory to two rows (or one row plus one saved diagonal value). Why use the smallest of the three? A square with side 3 needs three overlapping squares with side 2 (above, left and diagonal). Any 0 in the 3 × 3 block makes one of those three smaller.

Which approach should you use?

Brute force is a good way to understand the problem. But the corner DP with the smallest of three neighbours is the answer interviewers expect. (LeetCode 221.)

Make it stick

Make it stick — close this page, then
  1. Write the state sentence and the rule for unique paths. Then change it for obstacles and for minimum path sum.
  2. Write 0/1 knapsack as a 2-D table. Then write it again with one row.
  3. Explain why the 0/1 loop goes from high capacity to low. Say what goes wrong if it does not.
  4. Turn “partition equal subset sum” into the question “can a subset add up to half the total?”
  5. Explain why coin change II loops over the amount upwards.
  6. Say which loop order counts combinations and which counts permutations. Say why.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

What's next

Tables with two numbers also fit problems on two strings. Let dp[i][j] describe the first i characters of one string and the first j characters of the other. Lesson 57 does this for longest common subsequence and edit distance. Then it comes back to the longest increasing subsequence with a faster O(n log n) method.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series