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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Minimum Path Sum Calculation

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

DSA Go

package main
import "fmt"
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))
}

A 7

B 8

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 dynamic programming. The path is 1 -> 3 -> 1 -> 1 -> 1 with sum 7.

❓ Predict Output

intermediate

Minimum Path Sum with Negative Values

What is the output of this Go code for minimum path sum when the grid contains negative values?

DSA Go

package main
import "fmt"
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))
}

A 1

B 2

C 0

D -1

💡 Hint

Negative values can reduce the path sum. Follow the minimum sums carefully.

The minimum path sum is -1 following path 1 -> -3 -> 1 -> -1 -> 1.

🔧 Debug

advanced

Identify the Error in Minimum Path Sum Code

What error will this Go code produce when run?

DSA Go

package main
import "fmt"
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))
}

A Compilation error: missing return statement

B Index out of range runtime panic

C Output is 7

D No error, outputs 8

💡 Hint

Check the loop conditions carefully for array indexing.

The loops use <= which causes index to go out of bounds causing runtime panic.

🧠 Conceptual

advanced

Why Dynamic Programming Works for Minimum Path Sum

Why is dynamic programming a suitable approach to solve the minimum path sum in a grid problem?

A Because it breaks the problem into overlapping subproblems and stores results to avoid recomputation

B Because it randomly selects paths and picks the minimum sum

C Because it sorts the grid cells to find the minimum path

D Because it uses recursion without storing intermediate results

💡 Hint

Think about how the problem can be divided into smaller parts.

Dynamic programming solves problems by breaking them into smaller overlapping subproblems and storing their solutions to avoid repeated work.

🚀 Application

expert

Minimum Path Sum with Obstacles

Given a grid where some cells are obstacles (represented by -1), which code modification correctly computes the minimum path sum avoiding obstacles? Assume movement only right or down.

DSA Go

package main
import "fmt"
func minPathSumWithObstacles(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == -1 {
                continue
            }
            if i == 0 && j == 0 {
                continue
            }
            up := 1<<31 - 1
            left := 1<<31 - 1
            if i > 0 && grid[i-1][j] != -1 {
                up = grid[i-1][j]
            }
            if j > 0 && grid[i][j-1] != -1 {
                left = grid[i][j-1]
            }
            minPrev := up
            if left < up {
                minPrev = left
            }
            if minPrev == 1<<31 - 1 {
                grid[i][j] = -1
            } else {
                grid[i][j] += minPrev
            }
        }
    }
    if grid[m-1][n-1] == -1 {
        return -1
    }
    return grid[m-1][n-1]
}

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

A -1

B 8

C 7

D 6

💡 Hint

Observe how obstacles affect reachability and path sums.

The obstacle at grid[1][1] does not block all paths to bottom-right, so the function computes the minimum path sum of 7.

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