Minimum Path Sum in Grid in DSA Typescript - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is the goal of the Minimum Path Sum problem in a grid?

To find the path from the top-left corner to the bottom-right corner of a grid that has the smallest possible sum of all numbers along the path, moving only down or right.

beginner

Which moves are allowed when finding the minimum path sum in a grid?

Only moves to the right or moves down are allowed at each step.

intermediate

How can dynamic programming help solve the Minimum Path Sum problem?

By storing the minimum path sums to each cell, we avoid recalculating paths multiple times, building the solution from the top-left to the bottom-right efficiently.

beginner

What is the base case when using dynamic programming for Minimum Path Sum in a grid?

The top-left cell's minimum path sum is its own value because it's the starting point.

intermediate

In the Minimum Path Sum problem, how do you calculate the minimum sum for a cell not in the first row or column?

Take the minimum of the sums from the cell above and the cell to the left, then add the current cell's value.

In the Minimum Path Sum problem, which directions can you move?

A Left and Down

B Left and Up

C Right and Up

D Right and Down

Only moves to the right or down are allowed to find the minimum path sum.

What is the minimum path sum for the starting cell in the grid?

A Zero

B The value of the starting cell

C The sum of all cells in the first row

D The sum of all cells in the first column

The starting cell's minimum path sum is its own value because it is the starting point.

How do you find the minimum path sum for a cell not in the first row or column?

A Add the current cell's value to the minimum of the sums from the cell above and the cell to the left

B Add the current cell's value to the sum from the cell above only

C Add the current cell's value to the sum from the cell to the left only

D Add the current cell's value to the maximum of the sums from the cell above and the cell to the left

We choose the smaller sum between the cell above and the cell to the left, then add the current cell's value.

Which technique is commonly used to solve the Minimum Path Sum problem efficiently?

A Dynamic Programming

B Brute Force

C Greedy Algorithm

D Divide and Conquer

Dynamic Programming stores intermediate results to avoid repeated calculations.

If the grid is [[1,3,1],[1,5,1],[4,2,1]], what is the minimum path sum?

A 8

B 9

C 7

D 10

The path 1→3→1→1→1 sums to 7, which is the minimum.

Explain how to use dynamic programming to find the minimum path sum in a grid.

Think about building the solution step-by-step from the start.

Describe the movement restrictions and why they matter in the Minimum Path Sum problem.

Consider how allowed moves affect possible paths.

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?
Given a grid of numbers, find the path from top-left to bottom-right with the smallest sum.

easy

A. The maximum number in the grid

B. The path with the smallest sum of numbers from top-left to bottom-right

C. The number of paths from top-left to bottom-right

D. The path with the largest sum of numbers from top-left to bottom-right

Solution

1. Step 1: Understand the problem goal

   The problem asks to find a path from the top-left corner to the bottom-right corner of the grid that has the smallest sum of all numbers along the path.

2. Step 2: Clarify path movement

   Movement is only allowed down or right at each step, so the path is constrained.

3. Final Answer:

   The path with the smallest sum of numbers from top-left to bottom-right -> Option B

4. Quick Check:

   Minimum path sum means smallest total sum [OK]

Hint: Look for smallest sum path from top-left to bottom-right [OK]

Common Mistakes:

• Confusing minimum with maximum sum
• Counting number of paths instead of sum
• Ignoring movement constraints (only right/down)

2. Which TypeScript syntax correctly initializes a 2D array named grid with values [[1,2],[3,4]]?

easy

A. const grid = [1,2,3,4];

B. const grid = new Array(1,2,3,4);

C. const grid = [[1,2],[3,4]];

D. const grid = Array(2,2);

Solution

1. Step 1: Understand 2D array initialization

   To create a 2D array with specific values, use nested arrays like [[1,2],[3,4]].

2. Step 2: Check each option

   const grid = [[1,2],[3,4]]; correctly uses nested arrays. Options B and D create arrays but not nested with those values. const grid = [1,2,3,4]; is a flat array.

3. Final Answer:

   const grid = [[1,2],[3,4]]; -> Option C

4. Quick Check:

   Nested arrays create 2D arrays [OK]

Hint: Use nested brackets for 2D arrays in TypeScript [OK]

Common Mistakes:

• Using flat arrays instead of nested arrays
• Using Array constructor incorrectly
• Confusing array length with array content

3. What is the minimum path sum for the grid below?

const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
];

medium

A. 7

B. 8

C. 9

D. 10

Solution

1. Step 1: Trace possible paths and sums

   Possible minimum path: 1 -> 3 -> 1 -> 1 -> 1 = 7 (wrong path, check carefully). Another path: 1 -> 1 -> 5 -> 1 -> 1 = 9. Correct minimum path is 1 -> 3 -> 1 -> 1 -> 1 = 7 is invalid because movement is only right/down. Let's check carefully:
   Path: (0,0)=1 -> (1,0)=1 -> (2,0)=4 -> (2,1)=2 -> (2,2)=1 sum=1+1+4+2+1=9
   Path: (0,0)=1 -> (0,1)=3 -> (0,2)=1 -> (1,2)=1 -> (2,2)=1 sum=1+3+1+1+1=7
   But movement only right/down, so path is valid.
   Check if any smaller sum exists.

2. Step 2: Confirm minimum sum

   The minimum path sum is 8 by moving right, down, down, right.
   Path: (0,0)=1 -> (0,1)=3 -> (1,1)=5 -> (2,1)=2 -> (2,2)=1 sum=1+3+5+2+1=12 (too large)
   Try path: (0,0)=1 -> (1,0)=1 -> (1,1)=5 -> (1,2)=1 -> (2,2)=1 sum=1+1+5+1+1=9
   Try path: (0,0)=1 -> (1,0)=1 -> (2,0)=4 -> (2,1)=2 -> (2,2)=1 sum=1+1+4+2+1=9
   Try path: (0,0)=1 -> (0,1)=3 -> (0,2)=1 -> (1,2)=1 -> (2,2)=1 sum=1+3+1+1+1=7 (valid)
   So minimum sum is 7.

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Sum of path 1->3->1->1->1 = 7 [OK]

Hint: Add numbers along right/down paths, pick smallest sum [OK]

Common Mistakes:

• Adding numbers from invalid paths (not only right/down)
• Forgetting to include starting cell value
• Mixing row and column indices

4. Identify the error in this TypeScript function to find minimum path sum:

function minPathSum(grid: number[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  const dp = Array(m).fill(Array(n).fill(0));
  dp[0][0] = grid[0][0];
  for (let i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
  for (let j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
    }
  }
  return dp[m-1][n-1];
}

medium

A. grid is not checked for empty input

B. Loop ranges are incorrect, should start from 0

C. Return statement returns wrong cell

D. dp array initialization shares references causing incorrect updates

Solution

1. Step 1: Analyze dp array initialization

   Using Array(m).fill(Array(n).fill(0)) creates m references to the same inner array, so updating one row updates all rows.

2. Step 2: Understand impact on dp updates

   Because all rows share the same array, dp updates overwrite each other, causing wrong results.

3. Final Answer:

   dp array initialization shares references causing incorrect updates -> Option D

4. Quick Check:

   Array.fill with objects shares references [OK]

Hint: Use loops or map to create independent inner arrays [OK]

Common Mistakes:

• Using fill for 2D array causes shared references
• Ignoring empty grid input checks
• Incorrect loop start indices

5. Given a grid:

const grid = [
  [2, 1, 3],
  [6, 5, 4],
  [7, 8, 9]
];

Write a TypeScript function to find the minimum path sum from top-left to bottom-right, moving only right or down. What is the minimum path sum?

hard

A. 19

B. 20

C. 21

D. 18

Solution

1. Step 1: Calculate dp values row-wise and column-wise

   Start dp[0][0] = 2.
   First row: dp[0][1] = 2+1=3, dp[0][2] = 3+3=6.
   First column: dp[1][0] = 2+6=8, dp[2][0] = 8+7=15.

2. Step 2: Fill remaining dp cells using min of top or left + current grid value

   dp[1][1] = min(dp[0][1], dp[1][0]) + 5 = min(3,8)+5=8
   dp[1][2] = min(dp[0][2], dp[1][1]) + 4 = min(6,8)+4=10
   dp[2][1] = min(dp[1][1], dp[2][0]) + 8 = min(8,15)+8=16
   dp[2][2] = min(dp[1][2], dp[2][1]) + 9 = min(10,16)+9=19

3. Final Answer:

   19 -> Option A

4. Quick Check:

   Minimum path sum dp[m-1][n-1] = 19 [OK]

Hint: Use dp table, fill from top-left to bottom-right [OK]

Common Mistakes:

• Adding values incorrectly in dp table
• Mixing up indices for rows and columns
• Not considering only right/down moves