Skip to main content
CodePeetCodePeet
CodePeet 250

Minimum Path Sum

MEDIUMProblemSolveExternal Links

Description

You are given a m × n grid filled with non-negative numbers. Your task is to find a path from the top-left corner (position grid[0][0]) to the bottom-right corner (position grid[m-1][n-1]) such that the sum of all numbers along the path is minimized.

Movement constraints:

  • At any point, you can only move down (to the next row) or right (to the next column)
  • You cannot move up, left, or diagonally

Every cell in the grid has a non-negative cost. You must step on the starting cell and the destination cell. Return the minimum possible sum along any valid path from start to finish.

3x3 grid showing cell values and the optimal path highlighted from top-left to bottom-right
3x3 grid showing cell values and the optimal path highlighted from top-left to bottom-right

Examples

Example 1

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

Output: 7

Explanation: The grid is 3×3. The optimal path is 1 → 3 → 1 → 1 → 1 (Right, Right, Down, Down), giving a sum of 1+3+1+1+1 = 7. Other paths like 1 → 1 → 4 → 2 → 1 (Down, Down, Right, Right) give sum = 9, and 1 → 1 → 5 → 1 → 1 (Down, Right, Right, Down) give sum = 9. The path along the top row then down the right column yields the minimum.

Example 2

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

Output: 12

Explanation: The grid is 2×3. The optimal path is 1 → 2 → 3 → 6 (Right, Right, Down), giving sum = 1+2+3+6 = 12. The other paths: 1 → 4 → 5 → 6 = 16 (Down, Right, Right), or 1 → 2 → 5 → 6 = 14 (Right, Down, Right), or 1 → 4 → 2 → 6... wait, we can't go up. So 12 is indeed the minimum.

Constraints

  • m == grid.length
  • n == grid[i].length
  • 1 ≤ m, n ≤ 200
  • 0 ≤ grid[i][j] ≤ 200

Editorial

Brute Force

Intuition

The most straightforward approach is to try every possible path and pick the one with the smallest sum. Since we can only move right or down, each path from the top-left to the bottom-right makes exactly (m-1) + (n-1) = m+n-2 moves. At each cell, we have at most two choices.

Define a recursive function dfs(i, j) that returns the minimum path sum from cell (i, j) to the bottom-right corner (m-1, n-1). The idea is:

  • If (i, j) is the destination → return grid[i][j] (we must include this cell's cost)
  • If (i, j) is out of bounds → return infinity (invalid path)
  • Otherwise: dfs(i, j) = grid[i][j] + min(dfs(i+1, j), dfs(i, j+1))

We take the current cell's value, then add the minimum cost of continuing downward or rightward. This explores every possible route.

Without memoization, the same cell (i, j) can be reached from many different earlier cells, so dfs(i, j) gets called multiple times for the same arguments. This leads to an exponential number of recursive calls.

Step-by-Step Explanation

Let's trace through with grid = [[1,3,1],[1,5,1],[4,2,1]] (3×3 grid):

Step 1: Call dfs(0,0). Current cell value = 1. Need min(dfs(1,0), dfs(0,1)). Explore dfs(1,0) first (go down).

Step 2: dfs(1,0): value = 1. Need min(dfs(2,0), dfs(1,1)). Explore dfs(2,0) first.

Step 3: dfs(2,0): value = 4. Need min(dfs(3,0), dfs(2,1)). dfs(3,0) = ∞ (out of bounds). Explore dfs(2,1).

Step 4: dfs(2,1): value = 2. Need min(dfs(3,1), dfs(2,2)). dfs(3,1) = ∞. dfs(2,2) = 1 (destination!). So dfs(2,1) = 2 + min(∞, 1) = 2 + 1 = 3.

Step 5: Back to dfs(2,0) = 4 + min(∞, 3) = 4 + 3 = 7.

Step 6: Now explore dfs(1,1): value = 5. Need min(dfs(2,1), dfs(1,2)). dfs(2,1) = 3 (REPEATED computation!).

Step 7: dfs(1,2): value = 1. Need min(dfs(2,2), dfs(1,3)). dfs(2,2) = 1 (REPEATED!). dfs(1,3) = ∞. dfs(1,2) = 1 + 1 = 2.

Step 8: dfs(1,1) = 5 + min(3, 2) = 5 + 2 = 7.

Step 9: dfs(1,0) = 1 + min(7, 7) = 1 + 7 = 8.

Step 10: Now explore dfs(0,1): value = 3. Need min(dfs(1,1), dfs(0,2)). dfs(1,1) = 7 (REPEATED!).

Step 11: dfs(0,2): value = 1. Need min(dfs(1,2), dfs(0,3)). dfs(1,2) = 2 (REPEATED!). dfs(0,3) = ∞. dfs(0,2) = 1 + 2 = 3.

Step 12: dfs(0,1) = 3 + min(7, 3) = 3 + 3 = 6.

Step 13: dfs(0,0) = 1 + min(8, 6) = 1 + 6 = 7. The minimum path sum is 7, following the path (0,0)→(0,1)→(0,2)→(1,2)→(2,2).

Minimum Path Sum — Recursive Exploration of All Paths — Watch the recursion explore all possible routes from (0,0) to (2,2). Each node shows the cell and its minimum path sum. Notice repeated computations of cells like (2,1), (2,2), (1,1), and (1,2).

Algorithm

  1. Define dfs(i, j) = minimum path sum from cell (i, j) to cell (m-1, n-1)
  2. Base cases:
    • If i ≥ m or j ≥ n → return ∞ (out of bounds, invalid path)
    • If i == m-1 and j == n-1 → return grid[i][j] (reached destination)
  3. Recursive case: dfs(i, j) = grid[i][j] + min(dfs(i+1, j), dfs(i, j+1))
  4. Return dfs(0, 0)

Code

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i >= m || j >= n)
                return INT_MAX;
            if (i == m - 1 && j == n - 1)
                return grid[i][j];
            return grid[i][j] + min(dfs(i + 1, j), dfs(i, j + 1));
        };
        
        return dfs(0, 0);
    }
};
class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n:
                return float('inf')
            if i == m - 1 and j == n - 1:
                return grid[i][j]
            return grid[i][j] + min(dfs(i + 1, j), dfs(i, j + 1))
        
        return dfs(0, 0)
class Solution {
    private int[][] grid;
    private int m, n;
    
    public int minPathSum(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        return dfs(0, 0);
    }
    
    private int dfs(int i, int j) {
        if (i >= m || j >= n)
            return Integer.MAX_VALUE;
        if (i == m - 1 && j == n - 1)
            return grid[i][j];
        return grid[i][j] + Math.min(dfs(i + 1, j), dfs(i, j + 1));
    }
}

Complexity Analysis

Time Complexity: O(2^(m+n))

At each cell, the recursion branches into two calls (down and right). The longest path has m+n-2 steps. Without memoization, cells are recomputed from different paths, leading to an exponential total number of calls. For a 200×200 grid, 2^398 is astronomically large.

Space Complexity: O(m + n)

The maximum depth of the recursion stack is m+n-2 (the longest path from start to destination). No additional data structures are used.

Why This Approach Is Not Efficient

The brute force runs in O(2^(m+n)) time, which is completely impractical for grids up to 200×200. Even for a tiny 10×10 grid, 2^18 = 262,144 calls, and it grows exponentially from there.

The problem is overlapping subproblems. The function dfs(i, j) depends only on the cell position (i, j), not on the path taken to reach it. Yet different paths to the same cell trigger separate computations. In our 3×3 example, dfs(2,1), dfs(2,2), dfs(1,1), and dfs(1,2) were all computed multiple times.

Since there are only m×n distinct cells, there are only m×n distinct subproblems. By caching results after the first computation, we ensure each cell is solved exactly once, reducing time from O(2^(m+n)) to O(m×n).

Better Approach - Top-Down DP (Memoized Recursion)

Intuition

We keep the exact same recursive logic but add a memo table. Before computing dfs(i, j), check if it is already in the cache. If yes, return the cached value. If no, compute it, store it, and return.

The recurrence remains:

  • dfs(i, j) = grid[i][j] + min(dfs(i+1, j), dfs(i, j+1))

With memoization, each of the m×n cells is computed exactly once. Each computation does O(1) work (one min operation, one addition, two lookups). The result is O(m×n) time — a dramatic improvement from exponential.

The memo table can be viewed as filling the DP table from bottom-right to top-left, but in the order dictated by the recursion (depth-first) rather than row-by-row.

Step-by-Step Explanation

Tracing with grid = [[1,3,1],[1,5,1],[4,2,1]] and memoization:

Step 1: dfs(0,0): not cached. Need min(dfs(1,0), dfs(0,1)). Start with dfs(1,0).

Step 2: dfs(1,0): not cached. Need min(dfs(2,0), dfs(1,1)). Start with dfs(2,0).

Step 3: dfs(2,0): not cached. Need min(dfs(3,0), dfs(2,1)). dfs(3,0)=∞. Need dfs(2,1).

Step 4: dfs(2,1): not cached. Need min(dfs(3,1), dfs(2,2)). dfs(3,1)=∞. dfs(2,2)=1 (base case). Cache: memo[2][2]=1. dfs(2,1) = 2+min(∞,1) = 3. Cache: memo[2][1]=3.

Step 5: dfs(2,0) = 4+min(∞,3) = 7. Cache: memo[2][0]=7.

Step 6: dfs(1,1): not cached. Need min(dfs(2,1), dfs(1,2)). dfs(2,1) → CACHE HIT: 3! No recomputation.

Step 7: dfs(1,2): not cached. Need min(dfs(2,2), dfs(1,3)). dfs(2,2) → CACHE HIT: 1! dfs(1,3)=∞. dfs(1,2) = 1+1 = 2. Cache: memo[1][2]=2.

Step 8: dfs(1,1) = 5+min(3,2) = 7. Cache: memo[1][1]=7.

Step 9: dfs(1,0) = 1+min(7,7) = 8. Cache: memo[1][0]=8.

Step 10: dfs(0,1): not cached. Need min(dfs(1,1), dfs(0,2)). dfs(1,1) → CACHE HIT: 7!

Step 11: dfs(0,2): not cached. Need min(dfs(1,2), dfs(0,3)). dfs(1,2) → CACHE HIT: 2! dfs(0,3)=∞. dfs(0,2) = 1+2 = 3. Cache: memo[0][2]=3.

Step 12: dfs(0,1) = 3+min(7,3) = 6. Cache: memo[0][1]=6.

Step 13: dfs(0,0) = 1+min(8,6) = 7. Each cell computed exactly once. 4 cache hits saved redundant work!

Minimum Path Sum — Memoized DP Table Filling Order — Watch the memo table fill as the recursion explores cells depth-first. Unlike bottom-up DP, the fill order follows the recursion — bottom-right cells resolve first. Cache hits prevent repeated work.

Algorithm

  1. Create a memo table of size m×n, initialized to -1 (or use @cache)
  2. Define dfs(i, j) with memoization:
    • If i ≥ m or j ≥ n → return ∞
    • If i == m-1 and j == n-1 → return grid[i][j]
    • If memo[i][j] ≠ -1 → return memo[i][j]
    • Compute result = grid[i][j] + min(dfs(i+1, j), dfs(i, j+1))
    • Store memo[i][j] = result and return
  3. Return dfs(0, 0)

Code

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> memo(m, vector<int>(n, -1));
        
        function<int(int, int)> dfs = [&](int i, int j) -> int {
            if (i >= m || j >= n)
                return INT_MAX;
            if (i == m - 1 && j == n - 1)
                return grid[i][j];
            if (memo[i][j] != -1)
                return memo[i][j];
            return memo[i][j] = grid[i][j] + min(dfs(i + 1, j), dfs(i, j + 1));
        };
        
        return dfs(0, 0);
    }
};
from functools import cache

class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        
        @cache
        def dfs(i: int, j: int) -> int:
            if i >= m or j >= n:
                return float('inf')
            if i == m - 1 and j == n - 1:
                return grid[i][j]
            return grid[i][j] + min(dfs(i + 1, j), dfs(i, j + 1))
        
        return dfs(0, 0)
class Solution {
    private int[][] grid;
    private int m, n;
    private int[][] memo;
    
    public int minPathSum(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        this.memo = new int[m][n];
        for (int[] row : memo)
            Arrays.fill(row, -1);
        return dfs(0, 0);
    }
    
    private int dfs(int i, int j) {
        if (i >= m || j >= n)
            return Integer.MAX_VALUE;
        if (i == m - 1 && j == n - 1)
            return grid[i][j];
        if (memo[i][j] != -1)
            return memo[i][j];
        return memo[i][j] = grid[i][j] + Math.min(dfs(i + 1, j), dfs(i, j + 1));
    }
}

Complexity Analysis

Time Complexity: O(m × n)

Each of the m×n cells is computed exactly once due to memoization. Each computation involves O(1) work (a min operation and an addition). Total: O(m×n).

Space Complexity: O(m × n)

The memo table stores up to m×n values. The recursion stack can be at most m+n-2 deep. Since m×n ≥ m+n for m, n ≥ 2, total space is O(m×n).

Why This Approach Is Not Efficient

The memoized approach achieves optimal O(m×n) time. However, there are practical downsides:

  1. Recursion overhead: Each recursive call has function call overhead (stack frame creation, argument passing). For a 200×200 grid, that is up to 40,000 recursive calls. While fast enough, an iterative approach avoids this overhead entirely.

  2. Stack depth risk: The maximum recursion depth is m+n-2 = 398 for the largest input (200×200). Python's default recursion limit is 1000, so it works, but it is uncomfortably close. Deeper recursions in other contexts could fail.

  3. Space optimization opportunity: The memo table uses O(m×n) space. When filling the DP table iteratively (bottom-up, row by row), we observe that each cell only depends on the cell below it and the cell to its right — or equivalently, when processing top-to-bottom, each cell depends on the cell above and to its left. This means we only need one row of data at a time, reducing space from O(m×n) to O(n).

Optimal Approach - Bottom-Up DP with Space Optimization

Intuition

Instead of recursion, we fill the DP table iteratively from top-left to bottom-right. Define dp[i][j] as the minimum path sum from (0,0) to (i,j). The recurrence is:

  • dp[0][0] = grid[0][0]
  • First row: dp[0][j] = dp[0][j-1] + grid[0][j] (can only come from left)
  • First column: dp[i][0] = dp[i-1][0] + grid[i][0] (can only come from above)
  • General: dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]

The key space optimization: dp[i][j] depends only on dp[i-1][j] (directly above) and dp[i][j-1] (directly left). We process rows left-to-right, top-to-bottom. Using a single 1D array dp[j]:

  • Before updating dp[j] for current row i, dp[j] still holds dp[i-1][j] (the value from the row above)
  • dp[j-1] has already been updated to dp[i][j-1] (the value from the left in the current row)

So dp[j] = min(dp[j], dp[j-1]) + grid[i][j] naturally uses both dependencies. For the first column (j=0), there is no left neighbor, so dp[0] = dp[0] + grid[i][0] (only from above).

We initialize dp[0] = 0 and all other values to infinity. Then for each cell: if it is the first column, dp[j] += grid[i][j]; otherwise dp[j] = min(dp[j], dp[j-1]) + grid[i][j].

This achieves O(m×n) time and O(n) space.

Step-by-Step Explanation

Let's trace through with grid = [[1,3,1],[1,5,1],[4,2,1]] using the 1D DP array:

Step 1: Initialize dp = [0, ∞, ∞]. dp[0]=0 means 'zero cost accumulated before starting'. All other positions are unreachable initially.

Step 2: Process row 0, j=0: First column, dp[0] = dp[0] + grid[0][0] = 0+1 = 1. dp = [1, ∞, ∞].

Step 3: Row 0, j=1: dp[1] = min(dp[1], dp[0]) + grid[0][1] = min(∞, 1) + 3 = 1+3 = 4. dp = [1, 4, ∞].

Step 4: Row 0, j=2: dp[2] = min(dp[2], dp[1]) + grid[0][2] = min(∞, 4) + 1 = 4+1 = 5. dp = [1, 4, 5].

Step 5: Process row 1, j=0: First column, dp[0] = dp[0] + grid[1][0] = 1+1 = 2. dp = [2, 4, 5].

Step 6: Row 1, j=1: dp[1] = min(dp1, dp0) + grid[1][1] = min(4,2) + 5 = 2+5 = 7. dp = [2, 7, 5].

Step 7: Row 1, j=2: dp[2] = min(dp2, dp1) + grid[1][2] = min(5,7) + 1 = 5+1 = 6. dp = [2, 7, 6].

Step 8: Process row 2, j=0: dp[0] = dp[0] + grid[2][0] = 2+4 = 6. dp = [6, 7, 6].

Step 9: Row 2, j=1: dp[1] = min(dp1, dp0) + grid[2][1] = min(7,6) + 2 = 6+2 = 8. dp = [6, 8, 6].

Step 10: Row 2, j=2: dp[2] = min(dp2, dp1) + grid[2][2] = min(6,8) + 1 = 6+1 = 7. dp = [6, 8, 7].

Step 11: Answer: dp[n-1] = dp[2] = 7.

Minimum Path Sum — 1D DP Array Row-by-Row Update — Watch a single 1D array get reused for each row. Before updating dp[j], it holds the 'from above' value. After dp[j-1] is updated, it holds the 'from left' value. The min() picks the cheaper direction.

Algorithm

  1. Create a 1D array dp of size n, initialized to infinity, except dp[0] = 0
  2. For each row i from 0 to m-1:
    • For each column j from 0 to n-1:
      • If j == 0: dp[j] = dp[j] + grid[i][j] (only from above)
      • Else: dp[j] = min(dp[j], dp[j-1]) + grid[i][j] (min of above and left)
  3. Return dp[n-1]

Code

class Solution {
public:
    int minPathSum(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> dp(n, INT_MAX);
        dp[0] = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[j] += grid[i][j];
                } else {
                    dp[j] = min(dp[j], dp[j - 1]) + grid[i][j];
                }
            }
        }
        
        return dp[n - 1];
    }
};
class Solution:
    def minPathSum(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        dp = [float('inf')] * n
        dp[0] = 0
        
        for i in range(m):
            for j in range(n):
                if j == 0:
                    dp[j] += grid[i][j]
                else:
                    dp[j] = min(dp[j], dp[j - 1]) + grid[i][j]
        
        return dp[n - 1]
class Solution {
    public int minPathSum(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] dp = new int[n];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (j == 0) {
                    dp[j] += grid[i][j];
                } else {
                    dp[j] = Math.min(dp[j], dp[j - 1]) + grid[i][j];
                }
            }
        }
        
        return dp[n - 1];
    }
}

Complexity Analysis

Time Complexity: O(m × n)

We iterate through each of the m×n cells exactly once. Each cell involves O(1) work: one comparison (min), one addition, and one assignment. Total: O(m×n). This is optimal — we must read every cell's value at least once to determine the path sum.

Space Complexity: O(n)

We use a single 1D array of size n, reused for every row. No recursion stack is needed (iterative approach). For the maximum input (200×200), this uses only 200 integers of storage instead of 40,000 — a 200× reduction in memory. If m > n, we could transpose the grid and use O(min(m,n)) space, but O(n) is already very efficient.