Minimum Path Sum

Medium15–20 min

Topics

Dynamic ProgrammingMatrix

Companies

AmazonMicrosoftAdobe

Given a grid where every cell holds a non-negative cost, and starting at the top-left corner with only right and down moves allowed, find the minimum possible total cost of any path to the bottom-right corner — the sum of every cell's cost along the way, including both endpoints. Every cell's cheapest total is its own cost plus whichever of the two cells that could lead into it — the one above, or the one to its left — offers the cheaper cost so far. The very first row and first column each only have one possible way in (straight along the edge), so their running totals are just a simple accumulation of costs with no comparison needed. Filling in the grid this way, one row at a time, means every cell's cheapest cost is already known by the time a later cell needs to compare against it, and the bottom-right corner ends up holding the answer.

Test Case 1:

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

Output:12

Explanation:The path 2→4→1→2→3 (right, right, down, down) totals 12, the smallest sum of any right/down route.

Test Case 2:

Input:grid = [[5,2],[7,3]]

Output:10

Explanation:The path 5→2→3 (right, down) totals 10, beating 5→7→3 (down, right) which totals 15.

Test Case 3:

Input:grid = [[9]]

Output:9

Explanation:A single-cell grid has only one possible path: the cell itself.

Constraints

◆1 ≤ grid.length, grid[0].length ≤ 50
◆0 ≤ grid[i][j] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Standing on any cell, the cheapest way to finish from there is that cell's own cost plus whichever of the two possible next moves — one step down or one step right — ends up cheaper overall. Reaching the bottom-right corner costs exactly that cell's own value, since there's nowhere left to go. Stepping past the bottom or right edge of the grid isn't a valid move, so that direction is simply excluded from the comparison whenever it would go out of bounds. Recursing from the top-left corner and always taking the cheaper of the two next moves at every cell finds the minimum total, though the same cell's cheapest cost ends up recomputed every time a different path reaches it.

TimeO(2^(m+n))

SpaceO(m + n)

Java

Try it out

class Solution {
    private int[][] grid;
    private int m;
    private int n;

    public int minPathSum(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        return solve(0, 0);
    }

    private int solve(int i, int j) {
        if (i == m - 1 && j == n - 1) return grid[i][j];
        if (i >= m || j >= n) return Integer.MAX_VALUE;
        int down = solve(i + 1, j);
        int right = solve(i, j + 1);
        return grid[i][j] + Math.min(down, right);
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for the row currently being processed, the cheapest cost to reach each column from the top-left corner. The very first column of every row can only be reached by moving straight down, so its cost simply adds this cell's value to whatever cost is already there from the row above. Every other cell chooses the cheaper of two arrivals — from above (the value already sitting at this column) or from the left (the value just computed at the previous column in this same row) — and adds its own cost on top. Sweeping through every row this way, the last column ends up holding the minimum total cost to the bottom-right corner.

TimeO(m × n)

SpaceO(n)