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.