Minimum Path Sum in Grid in DSA Go

Mental Model

Find the smallest total by moving only right or down from the top-left to the bottom-right of a grid.

Analogy: Imagine walking through a city grid where each block has a cost to cross. You want to pay the least total cost to reach your friend's house at the bottom-right corner by only moving east or south.

Start at top-left (S), move only -> or ↓, reach bottom-right (E).

[S][ ][ ]
[ ][ ][ ]
[ ][ ][E]

Dry Run Walkthrough

Input: grid: [[1,3,1],[1,5,1],[4,2,1]]

Goal: Find the path from top-left to bottom-right with the smallest sum of numbers by moving only right or down.

Step 1: Start at top-left cell with value 1

[1] -> 3 -> 1
1 -> 5 -> 1
4 -> 2 -> 1

Why: We begin at the starting point with cost 1

Step 2: Calculate minimum path sums for first row by moving right

[1] -> [4] -> [5]
1 -> 5 -> 1
4 -> 2 -> 1

Why: Only right moves possible in first row, so sums accumulate

Step 3: Calculate minimum path sums for first column by moving down

[1] -> 4 -> 5
[2] -> 5 -> 1
[6] -> 2 -> 1

Why: Only down moves possible in first column, sums accumulate

Step 4: Calculate minimum path sum for cell (1,1) by choosing min from top or left plus current cell

1 -> 4 -> 5
2 -> [7] -> 1
6 -> 2 -> 1

Why: Choose smaller sum between top (4) and left (2), add current cell (5)

Step 5: Calculate minimum path sum for cell (1,2)

1 -> 4 -> 5
2 -> 7 -> [6]
6 -> 2 -> 1

Why: Choose min between top (5) and left (7), add current cell (1)

Step 6: Calculate minimum path sum for cell (2,1)

1 -> 4 -> 5
2 -> 7 -> 6
6 -> [8] -> 1

Why: Choose min between top (7) and left (6), add current cell (2)

Step 7: Calculate minimum path sum for bottom-right cell (2,2)

1 -> 4 -> 5
2 -> 7 -> 6
6 -> 8 -> [7]

Why: Choose min between top (6) and left (8), add current cell (1)

Result:

Final minimum path sum grid:
1 -> 4 -> 5
2 -> 7 -> 6
6 -> 8 -> 7
Minimum path sum = 7

Annotated Code

DSA Go

package main

import (
	"fmt"
	"math"
)

type Grid [][]int

func minPathSum(grid Grid) int {
	rows := len(grid)
	cols := len(grid[0])

	// Update first row sums
	for c := 1; c < cols; c++ {
		grid[0][c] += grid[0][c-1] // accumulate sums moving right
	}

	// Update first column sums
	for r := 1; r < rows; r++ {
		grid[r][0] += grid[r-1][0] // accumulate sums moving down
	}

	// Calculate min path sums for rest of grid
	for r := 1; r < rows; r++ {
		for c := 1; c < cols; c++ {
			// choose min between top and left plus current cell
			grid[r][c] += int(math.Min(float64(grid[r-1][c]), float64(grid[r][c-1])))
		}
	}

	return grid[rows-1][cols-1] // bottom-right cell has min path sum
}

func main() {
	grid := Grid{
		{1, 3, 1},
		{1, 5, 1},
		{4, 2, 1},
	}
	result := minPathSum(grid)
	fmt.Println(result)
}

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

accumulate sums along first row by moving right

for r := 1; r < rows; r++ { grid[r][0] += grid[r-1][0] }

accumulate sums along first column by moving down

for r := 1; r < rows; r++ { for c := 1; c < cols; c++ { grid[r][c] += int(math.Min(float64(grid[r-1][c]), float64(grid[r][c-1]))) } }

for each cell, add minimum of top or left cell sums to current cell

return grid[rows-1][cols-1]

return minimum path sum at bottom-right cell

Output

7

Complexity Analysis

Time: O(m*n) because we visit each cell once to compute minimum sums

Space: O(1) because we update the grid in place without extra space

vs Alternative: Compared to recursive solutions without memoization which are exponential, this dynamic programming approach is efficient and uses constant extra space

Edge Cases

Empty grid

Function will panic due to accessing grid[0][0], so input should be validated before calling

Single cell grid

Returns the value of the single cell as minimum path sum

DSA Go

return grid[rows-1][cols-1]

Grid with one row

Sum accumulates moving right only along the single row

DSA Go

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

Grid with one column

Sum accumulates moving down only along the single column

DSA Go

for r := 1; r < rows; r++ {
	grid[r][0] += grid[r-1][0]
}

When to Use This Pattern

When you see a grid and need to find a path with minimum sum moving only right or down, use dynamic programming to build solutions from smaller subproblems.

Common Mistakes

Mistake: Not updating the first row and first column sums before filling the rest of the grid
Fix: Accumulate sums along first row and first column separately before processing inner cells

Mistake: Using recursion without memoization leading to timeouts
Fix: Use bottom-up dynamic programming to avoid repeated calculations

Summary

Calculates the minimum sum path from top-left to bottom-right in a grid moving only right or down.

Use when you need the cheapest path cost in a grid with movement constraints.

Build the solution by accumulating minimum sums row-wise and column-wise, then fill the rest using the minimum of top or left neighbors.

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