Minimum Path Sum in Grid in DSA C++

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, and you want to spend the least money walking from your home to a friend's house by only moving east or south.

Start:
[1] -> [3] -> [1]
 ↓      ↓      ↓
[1] -> [5] -> [1]
 ↓      ↓      ↓
[4] -> [2] -> [1]

You can only move -> or ↓ to reach bottom-right.

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 moving only right or down.

Step 1: Initialize first row by accumulating sums moving right

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

Why: We can only move right in the first row, so sums accumulate from left to right.

Step 2: Initialize first column by accumulating sums moving down

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

Why: We can only move down in the first column, so sums accumulate from top to bottom.

Step 3: 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: We pick the smaller sum path to reach this cell.

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

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

Why: Choose min path sum from top or left plus current cell value.

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

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

Why: Choose min path sum from top or left plus current cell value.

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

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

Why: Final cell sum is min of top or left plus current cell value.

Result:

Final grid with minimum path sums:
[1] -> [4] -> [5]
[2] -> [7] -> [8]
[6] -> [8] -> [9]
Minimum path sum = 9

Annotated Code

DSA C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        
        // Initialize first row sums
        for (int j = 1; j < n; j++) {
            grid[0][j] += grid[0][j - 1];
        }
        
        // Initialize first column sums
        for (int i = 1; i < m; i++) {
            grid[i][0] += grid[i - 1][0];
        }
        
        // Fill the rest of the grid with min path sums
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]);
            }
        }
        
        return grid[m - 1][n - 1];
    }
};

int main() {
    vector<vector<int>> grid = {{1,3,1},{1,5,1},{4,2,1}};
    Solution sol;
    int result = sol.minPathSum(grid);
    cout << "Minimum path sum = " << result << endl;
    return 0;
}

for (int j = 1; j < n; j++) { grid[0][j] += grid[0][j - 1]; }

Accumulate sums along the first row since only right moves are possible.

for (int i = 1; i < m; i++) { grid[i][0] += grid[i - 1][0]; }

Accumulate sums along the first column since only down moves are possible.

for (int i = 1; i < m; i++) { for (int j = 1; j < n; j++) { grid[i][j] += min(grid[i - 1][j], grid[i][j - 1]); } }

For each cell, add the minimum sum from the top or left neighbor to current cell value.

Output

Minimum path sum = 9

Complexity Analysis

Time: O(m*n) because we visit each cell once to compute the minimum path sum.

Space: O(1) because we update the input grid in place without extra storage.

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

Edge Cases

Empty grid

Function should handle gracefully or return 0 as no path exists.

DSA C++

int m = grid.size(); if (m == 0) return 0;

Single cell grid

Returns the value of the single cell as the minimum path sum.

DSA C++

int m = grid.size(); int n = grid[0].size(); if (m == 1 && n == 1) return grid[0][0];

Grid with all equal values

Minimum path sum is the sum along any path moving right and down.

DSA C++

No special guard needed; algorithm handles this naturally.

When to Use This Pattern

When asked to find the minimum cost path in a grid moving only right or down, use dynamic programming to build up solutions from the top-left corner.

Common Mistakes

Mistake: Not initializing the first row and first column sums before filling the rest of the grid.
Fix: Explicitly accumulate sums for the first row and first column before the main loop.

Mistake: Using max instead of min when choosing between top and left neighbors.
Fix: Use min to ensure the path sum is minimized.

Summary

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

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

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

Practice

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

easy

A. The largest sum of numbers along any path in the grid.

B. The shortest path length from top-left to bottom-right.

C. The number of paths from top-left to bottom-right.

D. The smallest sum of numbers along a path from top-left to bottom-right, moving only right or down.

Solution

1. Step 1: Understand the problem goal

   The problem asks for the minimum sum of values collected when moving from the top-left corner to the bottom-right corner of a grid, moving only right or down.

2. Step 2: Clarify movement constraints

   Only moves to the right or down are allowed, so the path is restricted and the sum depends on chosen cells.

3. Final Answer:

   The smallest sum of numbers along a path from top-left to bottom-right, moving only right or down. -> Option D

4. Quick Check:

   Minimum path sum = smallest sum path [OK]

Hint: Focus on sum along right/down moves only [OK]

Common Mistakes:

• Thinking diagonal moves are allowed
• Looking for maximum sum instead of minimum
• Counting number of paths instead of sum

2. Which of the following C++ code snippets correctly initializes a 2D vector named grid with 3 rows and 4 columns filled with zeros?

easy

A. std::vector grid(3, std::vector<int>(4, 0));

B. std::vector<int> grid(3, std::vector<int>(4, 0));

C. std::vector grid(4, std::vector<int>(3, 0));

D. std::vector grid(3, 4, 0);

Solution

1. Step 1: Understand 2D vector initialization syntax

   To create a 2D vector with 3 rows and 4 columns filled with zeros, we use vector of vectors: outer vector size 3, inner vector size 4, each element 0.

2. Step 2: Check each option

   std::vector grid(3, std::vector<int>(4, 0)); correctly uses std::vector grid(3, std::vector<int>(4, 0)); which means 3 rows, each row is a vector of 4 zeros.

3. Final Answer:

   std::vector grid(3, std::vector<int>(4, 0)); -> Option A

4. Quick Check:

   Correct 2D vector init = std::vector grid(3, std::vector<int>(4, 0)); [OK]

Hint: Use vector of vectors with inner vector size and default value [OK]

Common Mistakes:

• Using wrong vector type for 2D
• Swapping rows and columns sizes
• Trying to pass three arguments to vector constructor

3. What is the output of the following C++ code that calculates the minimum path sum in a 2x2 grid?

std::vector grid = {{1, 3}, {1, 5}};
int m = grid.size();
int n = grid[0].size();
for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    grid[i][j] += std::min(grid[i-1][j], grid[i][j-1]);
  }
}
std::cout << grid[m-1][n-1] << std::endl;

medium

A. 7

B. 8

C. 9

D. 10

Solution

1. Step 1: Calculate first column cumulative sums

   grid[1][0] = grid[1][0] + grid[0][0] = 1 + 1 = 2

2. Step 2: Calculate first row cumulative sums

   grid[0][1] = grid[0][1] + grid[0][0] = 3 + 1 = 4

3. Step 3: Calculate inner cell minimum path sums

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

4. Final Answer:

   7 -> Option A

5. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Update first row and column cumulatively, then inner cells [OK]

Common Mistakes:

• Not updating first row and column before inner cells
• Adding max instead of min
• Mixing indices i and j

4. The following code attempts to compute the minimum path sum in a grid but has a bug. What is the error?

std::vector grid = {{1, 2, 3}, {4, 5, 6}};
int m = grid.size();
int n = grid[0].size();
for (int i = 1; i < m; i++) grid[i][0] += grid[i-1][0];
for (int j = 1; j < n; j++) grid[0][j] += grid[0][j-1];
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    grid[i][j] += std::max(grid[i-1][j], grid[i][j-1]);
  }
}
std::cout << grid[m-1][n-1] << std::endl;

medium

A. Wrong loop ranges for i and j

B. Not initializing first row and column

C. Using std::max instead of std::min in inner loop

D. Incorrect grid initialization syntax

Solution

1. Step 1: Check the inner loop operation

   The code uses std::max to update grid[i][j], but the problem requires minimum path sum, so std::min should be used.

2. Step 2: Verify other parts

   First row and column are correctly initialized, loops have correct ranges, and grid initialization is valid.

3. Final Answer:

   Using std::max instead of std::min in inner loop -> Option C

4. Quick Check:

   Use min for minimum path sum [OK]

Hint: Use min, not max, when updating path sums [OK]

Common Mistakes:

• Confusing max and min functions
• Skipping first row/column initialization
• Off-by-one errors in loops

5. Given the grid below, what is the minimum path sum from top-left to bottom-right?

grid = {
  {1, 3, 1, 2},
  {1, 5, 1, 1},
  {4, 2, 1, 3}
};

You can only move right or down. Calculate the minimum sum.

hard

A. 8

B. 10

C. 9

D. 11

Solution

1. Step 1: Compute first row and first column cumulative sums

   First row: [1, 4, 5, 7] (1, 1+3=4, 4+1=5, 5+2=7) First column: [1, 2, 6] (1, 1+1=2, 2+4=6)

2. Step 2: Calculate inner cells minimum path sums

   Row 1, col 1: 5 + min(4,2) = 5 + 2 = 7 Row 1, col 2: 1 + min(5,7) = 1 + 5 = 6 Row 1, col 3: 1 + min(7,6) = 1 + 6 = 7 Row 2, col 1: 2 + min(7,6) = 2 + 6 = 8 Row 2, col 2: 1 + min(6,8) = 1 + 6 = 7 Row 2, col 3: 3 + min(7,7) = 3 + 7 = 10

3. Final Answer:

   10 -> Option B

4. Quick Check:

   Minimum path sum = 10 [OK]

Hint: Fill first row/column, then inner cells with min sums [OK]

Common Mistakes:

• Adding max instead of min
• Incorrect cumulative sums for first row/column
• Misindexing grid cells