Minimum Path Sum in Grid in DSA Go - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the first cell of the dp grid with the grid's first cell value.

DSA Go

dp[0][0] = grid[1][0][0]

Drag options to blanks, or click blank then click option'

A+

B[

C-

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Using '+' or '*' instead of indexing brackets.

Trying to assign dp[0][0] a value without indexing grid.

We assign dp[0][0] the value of grid[0][0] to start the minimum path sum calculation.

2fill in blank

medium

Complete the code to fill the first row of dp by adding the current grid cell to the previous dp cell.

DSA Go

for j := 1; j < cols; j++ {
    dp[0][j] = dp[0][j-1] [1] grid[0][j]
}

Drag options to blanks, or click blank then click option'

A-

B/

C*

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Using wrong indices for dp or grid.

We add the current grid cell value to the previous dp cell to accumulate the path sum along the first row.

3fill in blank

hard

Fix the error in the nested loop to correctly compute dp[i][j] as the minimum path sum from top or left plus current grid value.

DSA Go

for i := 1; i < rows; i++ {
    for j := 1; j < cols; j++ {
        dp[i][j] = min(dp[i-1][j], dp[i][j-1]) [1] grid[i][j]
    }
}

Drag options to blanks, or click blank then click option'

A*

B-

C+

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting to add the current grid cell value.

We add the current grid cell value to the minimum of the top and left dp cells to get the minimum path sum at dp[i][j].

4fill in blank

hard

Fill both blanks to define the min function and use it to find the smaller of two integers.

DSA Go

func min(a, b int) int {
    if a [1] b {
        return a
    }
    return [2]
}

Drag options to blanks, or click blank then click option'

A<

B>

Ca

Db

Attempts:

3 left

💡 Hint

Common Mistakes

Using '>' instead of '<' in the if condition.

Returning 'a' in the else case instead of 'b'.

The min function returns a if a is less than b; otherwise, it returns b.

5fill in blank

hard

Fill all three blanks to complete the function that returns the minimum path sum from top-left to bottom-right in the grid.

DSA Go

func minPathSum(grid [][]int) int {
    rows, cols := len(grid), len(grid[0])
    dp := make([][]int, rows)
    for i := 0; i < rows; i++ {
        dp[i] = make([]int, cols)
    }
    dp[0][0] = grid[0][0]

    for j := 1; j < cols; j++ {
        dp[0][j] = dp[0][j-1] [1] grid[0][j]
    }

    for i := 1; i < rows; i++ {
        dp[i][0] = dp[i-1][0] [2] grid[i][0]
    }

    for i := 1; i < rows; i++ {
        for j := 1; j < cols; j++ {
            dp[i][j] = min(dp[i-1][j], dp[i][j-1]) [3] grid[i][j]
        }
    }

    return dp[rows-1][cols-1]
}

Drag options to blanks, or click blank then click option'

A+

B-

C*

D/

Attempts:

3 left

💡 Hint

Common Mistakes

Using subtraction or multiplication instead of addition.

Forgetting to add grid values to dp cells.

All additions accumulate the path sums correctly: first row, first column, and inner cells.

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