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

Minimum Path Sum in Grid

📖 Scenario: Imagine you are helping a robot find the easiest path through a grid of numbers. Each number represents the cost to step on that square. 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, moving only right or down.

📋 What You'll Learn

Create a 2D slice called grid with exact values

Create a variable rows and cols for grid dimensions

Use nested for loops to compute minimum path sums

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

💡 Why This Matters

🌍 Real World

Finding the cheapest or easiest path in maps, games, or robot navigation systems.

💼 Career

Understanding grid traversal and dynamic programming is useful in software development, especially in fields like AI, robotics, and game development.

1

Create the grid

Create a 2D slice of integers called grid with these exact values: {{1,3,1}, {1,5,1}, {4,2,1}}

DSA Go

# Create the grid variable with the given values
# Your code here

Hint

Use a slice of slices to create the 2D grid.

2

Set grid dimensions

Create two variables called rows and cols that store the number of rows and columns in grid respectively.

DSA Go

package main

import "fmt"

func main() {
    grid := [][]int{{1,3,1}, {1,5,1}, {4,2,1}}
    // Set rows and cols variables
    // Your code here
}

Hint

Use len(grid) for rows and len(grid[0]) for columns.

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. Use these rules:
- For the first row (r == 0), add the value from the left cell.
- For the first column (c == 0), add the value from the above cell.
- For other cells, add the minimum of the top or left cell values.

DSA Go

package main

import "fmt"

func main() {
    grid := [][]int{{1,3,1}, {1,5,1}, {4,2,1}}
    rows := len(grid)
    cols := len(grid[0])
    // Use nested for loops with r and c to update grid
    // Your code here
}

Hint

Update each cell by adding the minimum path sum from the top or left neighbor.

4

Print the minimum path sum

Print the value in the bottom-right cell of grid using fmt.Println. This value is the minimum path sum.

DSA Go

package main

import "fmt"

func main() {
    grid := [][]int{{1,3,1}, {1,5,1}, {4,2,1}}
    rows := len(grid)
    cols := len(grid[0])

    for r := 0; r  0 {
                grid[r][c] += grid[r][c-1]
            } else if c == 0 && r > 0 {
                grid[r][c] += grid[r-1][c]
            } else if r > 0 && c > 0 {
                if grid[r-1][c] < grid[r][c-1] {
                    grid[r][c] += grid[r-1][c]
                } else {
                    grid[r][c] += grid[r][c-1]
                }
            }
        }
    }
    // Print the minimum path sum
    fmt.Println(grid[rows-1][cols-1])
}

Hint

The bottom-right cell contains the minimum path sum after updates.

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?

easy

A. The number of paths from top-left to bottom-right moving only left or up

B. The largest sum of numbers from the top-left to bottom-right moving only diagonally

C. The smallest sum of numbers from the top-left to bottom-right moving only right or down

D. The sum of all numbers in the grid

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Recognize allowed moves

   Only moves to the right or down are allowed, so the path must follow these directions.

3. Final Answer:

   The smallest sum of numbers from the top-left to bottom-right moving only right or down -> Option C

4. Quick Check:

   Minimum path sum = smallest total sum [OK]

Hint: Focus on moves right or down to find smallest sum path [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Looking for largest sum instead of smallest
• Counting all numbers instead of path sum

2. Which of the following Go code snippets correctly initializes a 2D grid for the Minimum Path Sum problem?

easy

A. grid := [3][3]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}

B. grid := []int{ {1, 3, 1}, {1, 5, 1}, {4, 2, 1} }

C. grid := [][]int{1, 3, 1, 1, 5, 1, 4, 2, 1}

D. grid := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}}

Solution

1. Step 1: Check correct 2D slice initialization

   grid := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}} uses [][]int with nested slices, which is the correct way to declare a 2D slice in Go.

2. Step 2: Identify incorrect options

   grid := [3][3]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}} uses fixed array type which is valid but less flexible; grid := [][]int{1, 3, 1, 1, 5, 1, 4, 2, 1} is a flat slice, not 2D; grid := []int{ {1, 3, 1}, {1, 5, 1}, {4, 2, 1} } uses []int with nested braces which is invalid syntax.

3. Final Answer:

   grid := [][]int{{1, 3, 1}, {1, 5, 1}, {4, 2, 1}} -> Option D

4. Quick Check:

   2D slice with nested slices = correct grid init [OK]

Hint: Use [][]int with nested braces for 2D slices [OK]

Common Mistakes:

• Using flat slices instead of 2D slices
• Incorrect array type syntax
• Missing nested braces for rows

3. What is the output of the following Go code that calculates the minimum path sum?

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    for i := 1; i < m; i++ {
        grid[i][0] += grid[i-1][0]
    }
    for j := 1; j < n; j++ {
        grid[0][j] += grid[0][j-1]
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if grid[i-1][j] < grid[i][j-1] {
                grid[i][j] += grid[i-1][j]
            } else {
                grid[i][j] += grid[i][j-1]
            }
        }
    }
    return grid[m-1][n-1]
}

func main() {
    grid := [][]int{{1,3,1},{1,5,1},{4,2,1}}
    fmt.Println(minPathSum(grid))
}

medium

A. 7

B. 8

C. 9

D. 10

Solution

1. Step 1: Calculate first column cumulative sums

   grid[1][0] = 1+1=2, grid[2][0] = 2+4=6

2. Step 2: Calculate first row cumulative sums

   grid[0][1] = 1+3=4, grid[0][2] = 4+1=5

3. Step 3: Calculate remaining cells minimum path sums

   grid[1][1] = min(4,2)+5=7, grid[1][2] = min(5,7)+1=6, grid[2][1] = min(7,6)+2=8, grid[2][2] = min(6,8)+1=7

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill first row and column, then choose min of top or left [OK]

Common Mistakes:

• Not updating first row and column sums
• Adding max instead of min
• Mixing indices in loops

4. Find the error in this Go function for minimum path sum and select the fix:

func minPathSum(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    for i := 1; i <= m; i++ {
        grid[i][0] += grid[i-1][0]
    }
    for j := 1; j <= n; j++ {
        grid[0][j] += grid[0][j-1]
    }
    for i := 1; i < m; i++ {
        for j := 1; j < n; j++ {
            if grid[i-1][j] < grid[i][j-1] {
                grid[i][j] += grid[i-1][j]
            } else {
                grid[i][j] += grid[i][j-1]
            }
        }
    }
    return grid[m-1][n-1]
}

medium

A. Initialize grid with zeros before loops

B. Change loops to use < instead of <= for i and j

C. Add else if condition for equal values

D. Return grid[0][0] instead of grid[m-1][n-1]

Solution

1. Step 1: Identify loop boundary error

   The loops use <= which causes index out of range error because valid indices are 0 to m-1 and 0 to n-1.

2. Step 2: Fix loop conditions

   Changing loops to use < instead of <= prevents out of range access and correctly iterates over grid indices.

3. Final Answer:

   Change loops to use < instead of <= for i and j -> Option B

4. Quick Check:

   Loop indices must be less than length [OK]

Hint: Use < length, not <= length in loops [OK]

Common Mistakes:

• Using <= causing index out of range
• Not checking array bounds
• Returning wrong grid cell

5. Given a grid with some cells having zero cost, how does the presence of zero values affect the minimum path sum calculation? Example grid:

[[1, 0, 3],
 [0, 5, 1],
 [4, 2, 0]]

Choose the correct statement.

hard

A. Zero cost cells can reduce the minimum path sum by providing cheaper paths

B. Zero cost cells are ignored in the calculation

C. Zero cost cells cause the algorithm to fail due to division by zero

D. Zero cost cells increase the minimum path sum

Solution

1. Step 1: Understand zero cost cell effect

   Cells with zero cost add no extra sum, so paths passing through them can have lower total sums.

2. Step 2: Confirm algorithm behavior

   The algorithm sums cell values; zero values reduce total sum, so zero cost cells help find cheaper paths.

3. Final Answer:

   Zero cost cells can reduce the minimum path sum by providing cheaper paths -> Option A

4. Quick Check:

   Zero cost cells lower path sum [OK]

Hint: Zero cells lower path sum by adding no cost [OK]

Common Mistakes:

• Ignoring zero cells in sum
• Assuming zero causes errors
• Thinking zero increases cost