Minimum Path Sum in Grid in DSA Typescript - Build from Scratch

Minimum Path Sum in Grid

📖 Scenario: Imagine you are helping a delivery robot find the easiest path through a city grid. Each cell in the grid has a cost representing how hard it is to cross. The robot can only move right or down. Your job is to help the robot find the path with the smallest total cost from the top-left corner to the bottom-right corner.

🎯 Goal: Build a program that calculates the minimum path sum in a grid by moving only right or down.

📋 What You'll Learn

Create a 2D array called grid with exact values

Create a variable called rows and set it to the number of rows in grid

Create a variable called cols and set it to the number of columns in grid

Use nested for loops with variables r and c to update grid with minimum path sums

Print the minimum path sum from the top-left to bottom-right cell

💡 Why This Matters

🌍 Real World

Finding the easiest or cheapest path through a grid is useful in robotics, GPS navigation, and game development.

💼 Career

Understanding grid traversal and dynamic programming is important for software engineers working on pathfinding algorithms and optimization problems.

1

Create the grid

Create a 2D array called grid with these exact values: [[1,3,1],[1,5,1],[4,2,1]]

DSA Typescript

# Your code here

Hint

Use const grid: number[][] = [[1,3,1],[1,5,1],[4,2,1]]; to create the grid.

2

Set rows and columns variables

Create a variable called rows and set it to the number of rows in grid. Then create a variable called cols and set it to the number of columns in grid.

DSA Typescript

const grid: number[][] = [[1,3,1],[1,5,1],[4,2,1]];
# Your code here

Hint

Use const rows = grid.length; and const cols = grid[0].length;.

3

Calculate minimum path sums

Use nested for loops with variables r and c to update grid so each cell contains the minimum path sum to reach it from the top-left corner. Handle the first row and first column separately.

DSA Typescript

const grid: number[][] = [[1,3,1],[1,5,1],[4,2,1]];
const rows: number = grid.length;
const cols: number = grid[0].length;
# Your code here

Hint

First update the first column by adding the cell above. Then update the first row by adding the cell to the left. Finally, update the rest by adding the minimum of the top or left cell.

4

Print the minimum path sum

Print the minimum path sum from the top-left to bottom-right cell by printing grid[rows - 1][cols - 1].

DSA Typescript

const grid: number[][] = [[1,3,1],[1,5,1],[4,2,1]];
const rows: number = grid.length;
const cols: number = grid[0].length;

for (let r = 1; r < rows; r++) {
    grid[r][0] += grid[r - 1][0];
}

for (let c = 1; c < cols; c++) {
    grid[0][c] += grid[0][c - 1];
}

for (let r = 1; r < rows; r++) {
    for (let c = 1; c < cols; c++) {
        grid[r][c] += Math.min(grid[r - 1][c], grid[r][c - 1]);
    }
}
# Your code here

Hint

Print the value at the bottom-right corner of the grid using console.log(grid[rows - 1][cols - 1]);.