Minimum Path Sum in Grid in DSA Typescript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Path Sum Calculation

What is the output of the following TypeScript code that calculates the minimum path sum in a 3x3 grid?

DSA Typescript

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

const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
];
console.log(minPathSum(grid));

A 8

B 7

C 9

D 6

💡 Hint

Trace the path from top-left to bottom-right, adding the smallest sums step by step.

The minimum path sum is calculated by accumulating the smallest sums from the top-left corner to the bottom-right corner. The path is 1 → 3 → 1 → 1 → 1, which sums to 7.

🧠 Conceptual

intermediate

Understanding the Movement Constraints

In the Minimum Path Sum problem, which movements are allowed when moving from the top-left corner to the bottom-right corner of the grid?

A Only moves diagonally

B Moves in all four directions: up, down, left, right

C Only moves to the right or down

D Moves to the right, down, and diagonally

💡 Hint

Think about the problem constraints that simplify the path choices.

The problem restricts movement to only right or down to ensure a unique path and simplify calculations.

🔧 Debug

advanced

Identify the Error in the Minimum Path Sum Code

What error will the following TypeScript code produce when run, and why?

DSA Typescript

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

const grid = [
  [1, 3, 1],
  [1, 5, 1],
  [4, 2, 1]
];
console.log(minPathSum(grid));

A TypeError: Cannot read property '0' of undefined

B SyntaxError: Unexpected token

C Returns incorrect minimum path sum

D No error, outputs 7

💡 Hint

Check the loop conditions and array indexing carefully.

The loops use <= which causes index out of bounds access, leading to undefined elements and a TypeError when trying to access grid[i][0].

🚀 Application

advanced

Minimum Path Sum in a Larger Grid

Given the following 4x4 grid, what is the minimum path sum from top-left to bottom-right?

DSA Typescript

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

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

console.log(minPathSum(grid));

A 10

B 15

C 14

D 12

💡 Hint

Calculate cumulative sums row-wise and column-wise, then fill the rest using minimum of top and left cells.

The minimum path sum is 10, following the path 1 → 2 → 2 → 1 → 2 → 1 → 1.

❓ Predict Output

expert

Output of Minimum Path Sum with Negative Values

What is the output of the following TypeScript code that calculates the minimum path sum in a grid containing negative values?

DSA Typescript

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

const grid = [
  [2, -3, 1],
  [-5, 4, -2],
  [3, -1, 2]
];
console.log(minPathSum(grid));

A -1

B 1

C -2

D 0

💡 Hint

Consider how negative values affect the cumulative sums and path choices.

The minimum path sum is 0, following the path 2 → -3 → 1 → -2 → 2 with cumulative sums calculated carefully.

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