Minimum Path Sum in Grid in DSA Java

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, and you want to spend the least energy reaching your friend's house at the bottom-right corner by only moving east or south.

Start at top-left (S):
[S] -> [ ] -> [ ]
 ↓      ↓      ↓
[ ] -> [ ] -> [E]
S = start, E = end, arrows show allowed moves (right or down)

Dry Run Walkthrough

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

Goal: Find the minimum sum path from top-left to bottom-right 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 sums for cell (1,1) by choosing min from top or left plus current cell

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

Why: At (1,1), choose min(4,2) + 5 = 7 to get minimum sum path

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

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

Why: At (1,2), choose min(5,7) + 1 = 6 to get minimum sum path

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

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

Why: At (2,1), choose min(7,6) + 2 = 8 to get minimum sum path

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

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

Why: At (2,2), choose min(6,8) + 1 = 7 to get minimum sum path

Result:

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

Annotated Code

DSA Java

public class MinimumPathSum {
    public static int minPathSum(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        // 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];
        }

        // Calculate min path sums for rest of grid
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);
            }
        }

        return grid[m - 1][n - 1];
    }

    public static void main(String[] args) {
        int[][] grid = {
            {1, 3, 1},
            {1, 5, 1},
            {4, 2, 1}
        };
        int result = minPathSum(grid);
        System.out.println("Minimum path sum = " + result);
    }
}

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

accumulate sums along the first row since only right moves allowed

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

accumulate sums along the first column since only down moves allowed

grid[i][j] += Math.min(grid[i - 1][j], grid[i][j - 1]);

choose minimum sum from top or left cell and add current cell cost

Output

Minimum path sum = 7

Complexity Analysis

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

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

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

Edge Cases

Grid with only one cell

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

DSA Java

int m = grid.length; int n = grid[0].length;

Grid with one row

Accumulates sums moving right only along the single row

DSA Java

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

Grid with one column

Accumulates sums moving down only along the single column

DSA Java

for (int i = 1; i < m; i++) { grid[i][0] += grid[i - 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 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 cells
Fix: Use Math.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 to find minimum cost paths in a grid with movement restrictions.

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

Practice

1. What does the "Minimum Path Sum in Grid" problem ask you to find?
Given a grid of numbers, find the path from top-left to bottom-right with the smallest sum.

easy

A. The path with the smallest sum of numbers from top-left to bottom-right

B. The path with the largest sum of numbers from top-left to bottom-right

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

D. The maximum number in the grid

Solution

1. Step 1: Understand the problem goal

   The problem asks to find a path from the top-left cell to the bottom-right cell of a grid such that the sum of all numbers on the path is as small as possible.

2. Step 2: Clarify path movement

   Movement is only allowed down or right at each step, so the path is constrained.

3. Final Answer:

   The path with the smallest sum of numbers from top-left to bottom-right -> Option A

4. Quick Check:

   Minimum path sum means smallest total sum [OK]

Hint: Look for smallest sum path moving only right or down [OK]

Common Mistakes:

• Thinking the path can move diagonally or up
• Looking for maximum sum instead of minimum
• Counting number of paths instead of sum

2. Which of the following Java code snippets correctly initializes a 2D array named grid with 3 rows and 3 columns filled with zeros?

easy

A. int grid[][] = new int[3];

B. int[][] grid = new int[3][3];

C. int[] grid = new int[3][3];

D. int[][] grid = new int[3];

Solution

1. Step 1: Understand Java 2D array syntax

   In Java, a 2D array is declared as int[][] name = new int[rows][columns];. This creates a grid with specified rows and columns.

2. Step 2: Check each option

   int[][] grid = new int[3][3]; correctly declares a 3x3 int 2D array. Options A, C, and D have incorrect syntax or dimensions.

3. Final Answer:

   int[][] grid = new int[3][3]; -> Option B

4. Quick Check:

   Correct 2D array syntax = int[][] grid = new int[3][3]; [OK]

Hint: Use int[][] name = new int[rows][cols] for 2D arrays [OK]

Common Mistakes:

• Declaring 2D arrays with wrong brackets
• Initializing only one dimension
• Confusing 1D and 2D array syntax

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

int[][] grid = {{1, 3}, {1, 5}};
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) dp[i][0] = dp[i-1][0] + grid[i][0];
for (int j = 1; j < n; j++) dp[0][j] = dp[0][j-1] + grid[0][j];
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
}
System.out.println(dp[m-1][n-1]);

medium

A. 7

B. 8

C. 9

D. 10

Solution

1. Step 1: Initialize dp array with first row and column sums

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

2. Step 2: Calculate dp[1][1]

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

3. Final Answer:

   7 -> Option A

4. Quick Check:

   Minimum path sum = 7 [OK]

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

Common Mistakes:

• Adding max instead of min
• Not initializing first row and column correctly
• Mixing indices in loops

4. Identify the error in the following Java code snippet that tries to compute the minimum path sum in a grid:

int[][] grid = {{1,2,3},{4,5,6}};
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
for (int i = 1; i < m; i++) {
  dp[i][0] = dp[i-1][0] + grid[i][0];
}
for (int j = 1; j < n; j++) {
  dp[0][j] = dp[0][j-1] + grid[0][j];
}
for (int i = 1; i < m; i++) {
  for (int j = 1; j < n; j++) {
    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
  }
}

medium

A. Grid dimensions are wrong

B. Not initializing dp[0][0]

C. Loop ranges are incorrect

D. Using Math.max instead of Math.min in dp calculation

Solution

1. Step 1: Check dp initialization

   dp[0][0] is correctly initialized to grid[0][0]. Loops for first row and column are correct.

2. Step 2: Identify the error in dp update

   The inner loop uses Math.max instead of Math.min, which finds the maximum path sum, not minimum.

3. Final Answer:

   Using Math.max instead of Math.min in dp calculation -> Option D

4. Quick Check:

   Minimum path sum needs Math.min, not Math.max [OK]

Hint: Use Math.min to find minimum path sum, not Math.max [OK]

Common Mistakes:

• Using max instead of min in dp update
• Forgetting to initialize dp[0][0]
• Incorrect loop boundaries

5. Given a 3x3 grid:

int[][] grid = {
  {1, 2, 5},
  {3, 2, 1},
  {4, 1, 1}
};

What is the minimum path sum from top-left to bottom-right moving only right or down?

hard

A. 9

B. 8

C. 7

D. 10

Solution

1. Step 1: Initialize dp first row and column sums

   dp[0][0] = 1
   dp[0][1] = 1 + 2 = 3
   dp[0][2] = 3 + 5 = 8
   dp[1][0] = 1 + 3 = 4
   dp[2][0] = 4 + 4 = 8

2. Step 2: Calculate dp values for inner cells

   dp[1][1] = min(dp[0][1], dp[1][0]) + 2 = min(3,4) + 2 = 5
   dp[1][2] = min(dp[0][2], dp[1][1]) + 1 = min(8,5) + 1 = 6
   dp[2][1] = min(dp[1][1], dp[2][0]) + 1 = min(5,8) + 1 = 6
   dp[2][2] = min(dp[1][2], dp[2][1]) + 1 = min(6,6) + 1 = 7

3. Final Answer:

   7 -> Option C

4. Quick Check:

   Minimum path sum = 7 [OK]

Hint: Fill dp row and column first, then inner cells with min of top and left [OK]

Common Mistakes:

• Not updating dp correctly for inner cells
• Adding max instead of min
• Incorrect initialization of first row or column