DSA-137 · Read-only minimum-cost monotone grid with one-row DP

Minimum Path Sum

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 1642 deterministic checks. Learner drafts are not executed.

Understand the problem

Given a rectangular grid of nonnegative cell costs, return the minimum sum of a path from the upper-left cell to the lower-right cell, moving only right or down. Include the costs of both endpoints.

grid and every row must be non-null; null throws NullPointerException. The grid has at most 100000 rows and 100000 total cells. Rows must have equal length and costs must be nonnegative int values; ragged rows, negative costs, or excessive size throw IllegalArgumentException. Validate the complete shape and contents before empty handling.
Return an exact long minimum. An empty outer array or a rectangular zero-column grid returns zero by API convention; that value does not assert existence of a physical path. An existing one-cell grid returns that cell cost.
Only right/down moves are legal. Preserve all input values and row identities, including shared row objects. Equal row references still represent distinct coordinate rows. Return only a cost, not a chosen path; the recursive baseline is practical only for small grids.

Examples

Input: grid=[[1,3,1],[1,5,1],[4,2,1]]
Output: 7
One minimum path follows the top row then the final column: 1+3+1+1+1.
Input: grid=[[1,2,3],[4,5,6]]
Output: 12
Right,right,down costs 1+2+3+6.
Input: grid=[[2147483647,2147483647],[2147483647,2147483647]]
Output: 6442450941
Every route uses three cells; int accumulation would overflow.
Input: grid=[]
Output: 0
The empty-grid convention is not a path witness.

Before you start

Right/down DAG paths and prefix optimality
Boundary initialization and Java long promotion

Recognize the structure

Each cell has at most two incoming monotone path edges. A cheapest route to that cell must use a cheapest prefix to one of its predecessors; otherwise replacing the prefix improves the total. The dependency DAG makes a heap unnecessary for the reference. Unlike Unique Paths, alternatives are combined with minimum and the current cell cost is then added.

Try before revealing

Hint 1

What are the only two cells that can immediately precede an interior destination?

Hint 2

Write a minimum cost inclusive of the current cell, then initialize the unique boundary routes.

Hint 3

In one row, compare old dp[c] with new dp[c−1] and add the current cost as long.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate both final-move alternatives

Recursively compute the cheapest path into the destination from above or left, adding the destination cost. On the first row or column only one predecessor exists, and the origin returns its own cost. Explicit boundaries avoid fake zero-cost routes from outside the grid. The baseline revisits cells exponentially, with O(2^(R+C)) upper-bound time and O(R+C) live stack depth. Only small grids use it in verification. An independent Dijkstra search over right/down weighted edges checks the reference and includes the initial cell charge.

Improve the baseline

Define a cost inclusive of the current cell

M(r,c) is the minimum total paid from origin to (r,c), including grid[r][c]. M(0,0)=grid[0][0]. For a first-row cell add its cost to the previous first-row prefix; for a first-column cell add it to the prefix above. Zero-filled arrays are storage defaults, not valid minimum-path bases.

Choose an optimal incoming prefix

For an interior cell, M(r,c)=min(M(r−1,c),M(r,c−1))+grid[r][c]. Both alternatives append the same current cell, so minimizing their incoming costs is enough. Counting paths, minimizing cell count, or permitting arbitrary four-direction moves would define different problems.

Initialize boundaries before the interior scan

For the first row, explicitly accumulate dp[c]=dp[c−1]+grid[0][c]. Before each later row, increment dp[0] by its first cell cost. This makes all boundary values real reachable prefix costs and avoids Long.MAX_VALUE sentinels or sentinel-addition overflow.

Compress old up and new left

At interior (r,c), dp[c] is the previous row cost and dp[c−1] is the current row cost. Read both before assigning their minimum plus the int cell cost. The long predecessor promotes the addition before it occurs. Keep original row/column orientation; this implementation allocates C long entries rather than claiming a shorter-axis buffer.

Prove the numeric and ownership contracts

For a positive rectangle with RC≤100000, any monotone path contains R+C−1≤RC cells. Its sum is at most 100000×Integer.MAX_VALUE, safely within long. Validation scans all rows before optimization, and the algorithm only reads grid entries. Shared source rows are therefore safe and must not be cloned or overwritten in place.

Why it is correct

Boundary costs

The origin is visited once and pays its own cost. First-row and first-column cells have a unique monotone incoming route, so accumulating those exact sums is both feasible and optimal.

Optimal substructure

Every interior route ends from above or left. If its prefix were not optimal for that predecessor, replacing it with a cheaper prefix yields a legal cheaper route. Conversely either optimal predecessor prefix can append the current cell. Their minimum plus its cost is therefore exactly the optimum.

Rolling invariant and completion

Before updating column c in a later row, the buffer retains old up at c and new left at c−1. Left-to-right writes preserve that invariant. Finite row/column loops end with the complete destination cost. Bounds ensure all long additions are exact, and caller values and row references remain unchanged.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

import java.util.Objects;

public final class Solution {
    private Solution() {}
    private static int columns(int[][] grid) {
        Objects.requireNonNull(grid, "grid");
        if (grid.length > 100_000) throw new IllegalArgumentException("too many rows");
        int columns = grid.length == 0 ? 0 : Objects.requireNonNull(grid[0], "row").length;
        if ((long) grid.length * columns > 100_000) throw new IllegalArgumentException("too many cells");
        for (int[] row : grid) {
            Objects.requireNonNull(row, "row");
            if (row.length != columns) throw new IllegalArgumentException("ragged grid");
            for (int value : row) if (value < 0) throw new IllegalArgumentException("negative cell");
        }
        return columns;
    }
    public static long minPathSum(int[][] grid) {
        int width = columns(grid);
        if (grid.length == 0 || width == 0) return 0;
        long[] dp = new long[width];
        dp[0] = grid[0][0];
        for (int column = 1; column < width; column++) dp[column] = dp[column - 1] + grid[0][column];
        for (int row = 1; row < grid.length; row++) {
            dp[0] += grid[row][0];
            for (int column = 1; column < width; column++) dp[column] = Math.min(dp[column], dp[column - 1]) + grid[row][column];
        }
        return dp[width - 1];
    }
    // Baseline: enumerate monotone paths. Small grids only.
    public static long baseline(int[][] grid) {
        int width = columns(grid);
        if (grid.length == 0 || width == 0) return 0;
        return path(grid, grid.length - 1, width - 1);
    }
    private static long path(int[][] grid, int row, int column) {
        if (row == 0 && column == 0) return grid[0][0];
        if (row == 0) return path(grid, row, column - 1) + grid[row][column];
        if (column == 0) return path(grid, row - 1, column) + grid[row][column];
        return Math.min(path(grid, row - 1, column), path(grid, row, column - 1)) + grid[row][column];
    }
}

Read the meaningful blocks

Validate the whole matrix

columns checks outer and row nulls, rectangular shape, cell count using long multiplication, and every nonnegative entry. Even a zero-width first row does not hide a later null or ragged row.

Seed the origin and first row explicitly

dp[0] is the origin cost, not zero. The first-row loop builds actual prefix sums so an interior cell never reads an uninitialized cheaper fictitious route.

Advance one boundary and then the interior

Each new row first extends column zero. Interior updates compare the old and new buffer regions and add the current cost once. The final long value is returned without exposing the working array.

Complexity

For R rows and C columns, complete validation costs O(R+RC), and a nonempty-grid DP costs O(RC). Total time is O(R+RC+1), with O(C) auxiliary long storage for a positive grid and O(1) extra storage on empty/zero-width returns. Output is one long.

The recursive baseline has O(2^(R+C)) upper-bound time and O(R+C) call-stack space. A full DP table uses O(RC) extra storage and can retain path decisions; the value-only compressed row does not provide traceback. Input storage and displayed teaching snapshots are excluded from auxiliary-space claims.

Exact-state walkthroughs

Reveal normal and boundary traces

Optimal costs accumulate across rows

Input: [[1,3,1],[1,5,1],[4,2,1]] · Minimum inclusive path cost: 7

Step 1 of 17: Seed actual boundary state in a private row buffer.

Only the origin is seeded. Other zero buffer entries are uninitialized storage, not free paths. Caller grid values and row identities are unchanged.

Minimum path cost — real boundaries and inclusive cell charges

Phase: initial.

Read-only input: [[1,3,1],[1,5,1],[4,2,1]]. Costs include origin and destination. Rows and columns retain original coordinate meaning.

Conceptual minimum costs — · means uncomputed
Row / column	0	1	2
0	1	·	·
1	·	·	·
2	·	·	·

Actual one-row Java buffer

0: 1
1: 0 — unused storage, not a route
2: 0 — unused storage, not a route

The origin is seeded with its own cost; first-row and first-column routes are accumulated explicitly. Zero-filled storage must not supply phantom free paths. Old up and new left intentionally belong to different row versions. The complete table is explanatory history, not a reference allocation.

All source values stay unchanged. Full grids, old layers and history cards explain state meaning; they do not add to Java reference workspace. Exact counts and products use decimal strings in trace data.

State after this step
Variable	Value
input	`[[1,3,1],[1,5,1],[4,2,1]]`
phase	`"initial"`
height	`3`
width	`3`
table	`[[1,null,null],[null,null,null],[null,null,null]]`
dp	`[1,0,0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int columns(int[][] grid) {
 6         Objects.requireNonNull(grid, "grid");
 7         if (grid.length > 100_000) throw new IllegalArgumentException("too many rows");
 8         int columns = grid.length == 0 ? 0 : Objects.requireNonNull(grid[0], "row").length;
 9         if ((long) grid.length * columns > 100_000) throw new IllegalArgumentException("too many cells");
10         for (int[] row : grid) {
11             Objects.requireNonNull(row, "row");
12             if (row.length != columns) throw new IllegalArgumentException("ragged grid");
13             for (int value : row) if (value < 0) throw new IllegalArgumentException("negative cell");
14         }
15         return columns;
16     }
17     public static long minPathSum(int[][] grid) {
18         int width = columns(grid);
19         if (grid.length == 0 || width == 0) return 0;
20         long[] dp = new long[width];
21         dp[0] = grid[0][0];
22         for (int column = 1; column < width; column++) dp[column] = dp[column - 1] + grid[0][column];
23         for (int row = 1; row < grid.length; row++) {
24             dp[0] += grid[row][0];
25             for (int column = 1; column < width; column++) dp[column] = Math.min(dp[column], dp[column - 1]) + grid[row][column];
26         }
27         return dp[width - 1];
28     }
29     // Baseline: enumerate monotone paths. Small grids only.
30     public static long baseline(int[][] grid) {
31         int width = columns(grid);
32         if (grid.length == 0 || width == 0) return 0;
33         return path(grid, grid.length - 1, width - 1);
34     }
35     private static long path(int[][] grid, int row, int column) {
36         if (row == 0 && column == 0) return grid[0][0];
37         if (row == 0) return path(grid, row, column - 1) + grid[row][column];
38         if (column == 0) return path(grid, row - 1, column) + grid[row][column];
39         return Math.min(path(grid, row - 1, column), path(grid, row, column - 1)) + grid[row][column];
40     }
41 }
42

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed actual boundary state in a private row buffer.
Only the origin is seeded. Other zero buffer entries are uninitialized storage, not free paths. Caller grid values and row identities are unchanged.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"initial"
height
3
width
3
table
[[1,null,null],[null,null,null],[null,null,null]]
dp
[1,0,0]
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"candidate"
height
3
width
3
table
[[1,null,null],[null,null,null],[null,null,null]]
dp
[1,0,0]
row
0
column
1
up
null
left
1
cost
3
next
4
firstRow
true
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"commit"
height
3
width
3
table
[[1,4,null],[null,null,null],[null,null,null]]
dp
[1,4,0]
row
0
column
1
up
null
left
1
cost
3
next
4
firstRow
true
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"candidate"
height
3
width
3
table
[[1,4,null],[null,null,null],[null,null,null]]
dp
[1,4,0]
row
0
column
2
up
null
left
4
cost
1
next
5
firstRow
true
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"commit"
height
3
width
3
table
[[1,4,5],[null,null,null],[null,null,null]]
dp
[1,4,5]
row
0
column
2
up
null
left
4
cost
1
next
5
firstRow
true
Extend the unique first-column path.
There is no left predecessor at this boundary. The old up cost and current cell cost produce the new first-column total.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"boundary"
height
3
width
3
table
[[1,4,5],[2,null,null],[null,null,null]]
dp
[2,4,5]
row
1
column
0
up
1
cost
1
next
2
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"candidate"
height
3
width
3
table
[[1,4,5],[2,null,null],[null,null,null]]
dp
[2,4,5]
row
1
column
1
up
4
left
2
cost
5
next
7
firstRow
false
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"commit"
height
3
width
3
table
[[1,4,5],[2,7,null],[null,null,null]]
dp
[2,7,5]
row
1
column
1
up
4
left
2
cost
5
next
7
firstRow
false
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"candidate"
height
3
width
3
table
[[1,4,5],[2,7,null],[null,null,null]]
dp
[2,7,5]
row
1
column
2
up
5
left
7
cost
1
next
6
firstRow
false
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"commit"
height
3
width
3
table
[[1,4,5],[2,7,6],[null,null,null]]
dp
[2,7,6]
row
1
column
2
up
5
left
7
cost
1
next
6
firstRow
false
Extend the unique first-column path.
There is no left predecessor at this boundary. The old up cost and current cell cost produce the new first-column total.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"boundary"
height
3
width
3
table
[[1,4,5],[2,7,6],[6,null,null]]
dp
[6,7,6]
row
2
column
0
up
2
cost
4
next
6
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"candidate"
height
3
width
3
table
[[1,4,5],[2,7,6],[6,null,null]]
dp
[6,7,6]
row
2
column
1
up
7
left
6
cost
2
next
8
firstRow
false
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"commit"
height
3
width
3
table
[[1,4,5],[2,7,6],[6,8,null]]
dp
[6,8,6]
row
2
column
1
up
7
left
6
cost
2
next
8
firstRow
false
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"candidate"
height
3
width
3
table
[[1,4,5],[2,7,6],[6,8,null]]
dp
[6,8,6]
row
2
column
2
up
6
left
8
cost
1
next
7
firstRow
false
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"commit"
height
3
width
3
table
[[1,4,5],[2,7,6],[6,8,7]]
dp
[6,8,7]
row
2
column
2
up
6
left
8
cost
1
next
7
firstRow
false
Return the destination value from the final row.
The destination total includes both endpoints. A value-only row does not retain path reconstruction choices.
input
[[1,3,1],[1,5,1],[4,2,1]]
phase
"complete"
height
3
width
3
table
[[1,4,5],[2,7,6],[6,8,7]]
dp
[6,8,7]
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
7

Exact cost beyond int

Input: [[2147483647,2147483647],[2147483647,2147483647]] · Minimum inclusive path cost: 6442450941

Step 1 of 8: Seed actual boundary state in a private row buffer.

Only the origin is seeded. Other zero buffer entries are uninitialized storage, not free paths. Caller grid values and row identities are unchanged.

Minimum path cost — real boundaries and inclusive cell charges

Phase: initial.

Read-only input: [[2147483647,2147483647],[2147483647,2147483647]]. Costs include origin and destination. Rows and columns retain original coordinate meaning.

Conceptual minimum costs — · means uncomputed
Row / column	0	1
0	2147483647	·
1	·	·

Actual one-row Java buffer

0: 2147483647
1: 0 — unused storage, not a route

State after this step
Variable	Value
input	`[[2147483647,2147483647],[2147483647,2147483647]]`
phase	`"initial"`
height	`2`
width	`2`
table	`[[2147483647,null],[null,null]]`
dp	`[2147483647,0]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int columns(int[][] grid) {
 6         Objects.requireNonNull(grid, "grid");
 7         if (grid.length > 100_000) throw new IllegalArgumentException("too many rows");
 8         int columns = grid.length == 0 ? 0 : Objects.requireNonNull(grid[0], "row").length;
 9         if ((long) grid.length * columns > 100_000) throw new IllegalArgumentException("too many cells");
10         for (int[] row : grid) {
11             Objects.requireNonNull(row, "row");
12             if (row.length != columns) throw new IllegalArgumentException("ragged grid");
13             for (int value : row) if (value < 0) throw new IllegalArgumentException("negative cell");
14         }
15         return columns;
16     }
17     public static long minPathSum(int[][] grid) {
18         int width = columns(grid);
19         if (grid.length == 0 || width == 0) return 0;
20         long[] dp = new long[width];
21         dp[0] = grid[0][0];
22         for (int column = 1; column < width; column++) dp[column] = dp[column - 1] + grid[0][column];
23         for (int row = 1; row < grid.length; row++) {
24             dp[0] += grid[row][0];
25             for (int column = 1; column < width; column++) dp[column] = Math.min(dp[column], dp[column - 1]) + grid[row][column];
26         }
27         return dp[width - 1];
28     }
29     // Baseline: enumerate monotone paths. Small grids only.
30     public static long baseline(int[][] grid) {
31         int width = columns(grid);
32         if (grid.length == 0 || width == 0) return 0;
33         return path(grid, grid.length - 1, width - 1);
34     }
35     private static long path(int[][] grid, int row, int column) {
36         if (row == 0 && column == 0) return grid[0][0];
37         if (row == 0) return path(grid, row, column - 1) + grid[row][column];
38         if (column == 0) return path(grid, row - 1, column) + grid[row][column];
39         return Math.min(path(grid, row - 1, column), path(grid, row, column - 1)) + grid[row][column];
40     }
41 }
42

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Seed actual boundary state in a private row buffer.
Only the origin is seeded. Other zero buffer entries are uninitialized storage, not free paths. Caller grid values and row identities are unchanged.
input
[[2147483647,2147483647],[2147483647,2147483647]]
phase
"initial"
height
2
width
2
table
[[2147483647,null],[null,null]]
dp
[2147483647,0]
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[2147483647,2147483647],[2147483647,2147483647]]
phase
"candidate"
height
2
width
2
table
[[2147483647,null],[null,null]]
dp
[2147483647,0]
row
0
column
1
up
null
left
2147483647
cost
2147483647
next
4294967294
firstRow
true
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[2147483647,2147483647],[2147483647,2147483647]]
phase
"commit"
height
2
width
2
table
[[2147483647,4294967294],[null,null]]
dp
[2147483647,4294967294]
row
0
column
1
up
null
left
2147483647
cost
2147483647
next
4294967294
firstRow
true
Extend the unique first-column path.
There is no left predecessor at this boundary. The old up cost and current cell cost produce the new first-column total.
input
[[2147483647,2147483647],[2147483647,2147483647]]
phase
"boundary"
height
2
width
2
table
[[2147483647,4294967294],[4294967294,null]]
dp
[4294967294,4294967294]
row
1
column
0
up
2147483647
cost
2147483647
next
4294967294
Read the incoming finalized dependencies before writing this cell.
The first row has only a left predecessor. Interior cells minimize real incoming costs and then pay the current cell exactly once.
input
[[2147483647,2147483647],[2147483647,2147483647]]
phase
"candidate"
height
2
width
2
table
[[2147483647,4294967294],[4294967294,null]]
dp
[4294967294,4294967294]
row
1
column
1
up
4294967294
left
4294967294
cost
2147483647
next
6442450941
firstRow
false
Commit the cell to the row buffer and conceptual history.
Saved predecessor cards retain the values used; the live buffer now contains the new cell. The full table is teaching history rather than reference workspace.
input
[[2147483647,2147483647],[2147483647,2147483647]]
phase
"commit"
height
2
width
2
table
[[2147483647,4294967294],[4294967294,6442450941]]
dp
[4294967294,6442450941]
row
1
column
1
up
4294967294
left
4294967294
cost
2147483647
next
6442450941
firstRow
false
Return the destination value from the final row.
The destination total includes both endpoints. A value-only row does not retain path reconstruction choices.
input
[[2147483647,2147483647],[2147483647,2147483647]]
phase
"complete"
height
2
width
2
table
[[2147483647,4294967294],[4294967294,6442450941]]
dp
[4294967294,6442450941]
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
6442450941

Empty outer grid

Input: [] · Minimum inclusive path cost: 0

Step 1 of 2: Return the explicit zero-size contract result.

Validation precedes this outcome. Zero means no grid path for counting, and an empty-grid numeric convention for minimum cost. No row buffer is allocated.

Minimum path cost — real boundaries and inclusive cell charges

Phase: empty.

Read-only input: []. Costs include origin and destination. Rows and columns retain original coordinate meaning.

An empty/zero-width grid returns zero by API convention, without claiming a coordinate path exists. Validation has already completed; no buffer is allocated.

State after this step
Variable	Value
input	`[]`
phase	`"empty"`
height	`0`
width	`0`
table	`[]`
dp	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int columns(int[][] grid) {
 6         Objects.requireNonNull(grid, "grid");
 7         if (grid.length > 100_000) throw new IllegalArgumentException("too many rows");
 8         int columns = grid.length == 0 ? 0 : Objects.requireNonNull(grid[0], "row").length;
 9         if ((long) grid.length * columns > 100_000) throw new IllegalArgumentException("too many cells");
10         for (int[] row : grid) {
11             Objects.requireNonNull(row, "row");
12             if (row.length != columns) throw new IllegalArgumentException("ragged grid");
13             for (int value : row) if (value < 0) throw new IllegalArgumentException("negative cell");
14         }
15         return columns;
16     }
17     public static long minPathSum(int[][] grid) {
18         int width = columns(grid);
19         if (grid.length == 0 || width == 0) return 0;
20         long[] dp = new long[width];
21         dp[0] = grid[0][0];
22         for (int column = 1; column < width; column++) dp[column] = dp[column - 1] + grid[0][column];
23         for (int row = 1; row < grid.length; row++) {
24             dp[0] += grid[row][0];
25             for (int column = 1; column < width; column++) dp[column] = Math.min(dp[column], dp[column - 1]) + grid[row][column];
26         }
27         return dp[width - 1];
28     }
29     // Baseline: enumerate monotone paths. Small grids only.
30     public static long baseline(int[][] grid) {
31         int width = columns(grid);
32         if (grid.length == 0 || width == 0) return 0;
33         return path(grid, grid.length - 1, width - 1);
34     }
35     private static long path(int[][] grid, int row, int column) {
36         if (row == 0 && column == 0) return grid[0][0];
37         if (row == 0) return path(grid, row, column - 1) + grid[row][column];
38         if (column == 0) return path(grid, row - 1, column) + grid[row][column];
39         return Math.min(path(grid, row - 1, column), path(grid, row, column - 1)) + grid[row][column];
40     }
41 }
42

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Return the explicit zero-size contract result.
Validation precedes this outcome. Zero means no grid path for counting, and an empty-grid numeric convention for minimum cost. No row buffer is allocated.
input
[]
phase
"empty"
height
0
width
0
table
[]
dp
[]
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
0

Zero-width rectangular grid

Input: [[],[]] · Minimum inclusive path cost: 0

Step 1 of 2: Return the explicit zero-size contract result.

Validation precedes this outcome. Zero means no grid path for counting, and an empty-grid numeric convention for minimum cost. No row buffer is allocated.

Minimum path cost — real boundaries and inclusive cell charges

Phase: empty.

Read-only input: [[],[]]. Costs include origin and destination. Rows and columns retain original coordinate meaning.

An empty/zero-width grid returns zero by API convention, without claiming a coordinate path exists. Validation has already completed; no buffer is allocated.

State after this step
Variable	Value
input	`[[],[]]`
phase	`"empty"`
height	`2`
width	`0`
table	`[]`
dp	`[]`

See the affected Java block

 1 import java.util.Objects;
 2 
 3 public final class Solution {
 4     private Solution() {}
 5     private static int columns(int[][] grid) {
 6         Objects.requireNonNull(grid, "grid");
 7         if (grid.length > 100_000) throw new IllegalArgumentException("too many rows");
 8         int columns = grid.length == 0 ? 0 : Objects.requireNonNull(grid[0], "row").length;
 9         if ((long) grid.length * columns > 100_000) throw new IllegalArgumentException("too many cells");
10         for (int[] row : grid) {
11             Objects.requireNonNull(row, "row");
12             if (row.length != columns) throw new IllegalArgumentException("ragged grid");
13             for (int value : row) if (value < 0) throw new IllegalArgumentException("negative cell");
14         }
15         return columns;
16     }
17     public static long minPathSum(int[][] grid) {
18         int width = columns(grid);
19         if (grid.length == 0 || width == 0) return 0;
20         long[] dp = new long[width];
21         dp[0] = grid[0][0];
22         for (int column = 1; column < width; column++) dp[column] = dp[column - 1] + grid[0][column];
23         for (int row = 1; row < grid.length; row++) {
24             dp[0] += grid[row][0];
25             for (int column = 1; column < width; column++) dp[column] = Math.min(dp[column], dp[column - 1]) + grid[row][column];
26         }
27         return dp[width - 1];
28     }
29     // Baseline: enumerate monotone paths. Small grids only.
30     public static long baseline(int[][] grid) {
31         int width = columns(grid);
32         if (grid.length == 0 || width == 0) return 0;
33         return path(grid, grid.length - 1, width - 1);
34     }
35     private static long path(int[][] grid, int row, int column) {
36         if (row == 0 && column == 0) return grid[0][0];
37         if (row == 0) return path(grid, row, column - 1) + grid[row][column];
38         if (column == 0) return path(grid, row - 1, column) + grid[row][column];
39         return Math.min(path(grid, row - 1, column), path(grid, row, column - 1)) + grid[row][column];
40     }
41 }
42

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Return the explicit zero-size contract result.
Validation precedes this outcome. Zero means no grid path for counting, and an empty-grid numeric convention for minimum cost. No row buffer is allocated.
input
[[],[]]
phase
"empty"
height
2
width
0
table
[]
dp
[]
Return the documented result.
Complete tables, old layers and history cards explain the algorithm but are not extra Java workspace. Arbitrary-precision values use exact decimal strings in trace data.
result
0

Test the contract

Input: grid=[[]]
Output: 0
Rectangular zero-width convention.
Input: grid=[[5]]
Output: 5
One charged cell.
Input: grid=[[1,2,3]]
Output: 6
Unique first-row route.
Input: grid=[[1],[2],[3]]
Output: 6
Unique first-column route.
Input: grid=[[0,0],[0,0]]
Output: 0
Zero costs are valid.
Input: grid=[[1],[]]
Output: IllegalArgumentException
Reject ragged shape.

Common mistakes and counterexamples

Initialize all path costs to zero

Counterexample: A positive first-row cost could be bypassed by a nonexistent free predecessor.

Seed and accumulate real first-row/column routes.

Forget to include the origin or destination

Counterexample: [[5]] must return five, not zero.

Define the state as inclusive of its current cell.

Use int accumulation or add to an infinite sentinel

Counterexample: Three MAX_VALUE cells exceed int, and MAX_LONG+cost can wrap.

Use bounded long sums and explicit one-predecessor boundaries.

Write DP values into the caller grid

Counterexample: Shared source rows may alias, and the contract requires all values and identities unchanged.

Use a private long row buffer.

Follow-ups

Return one minimum path.

Store a complete cost table or predecessor directions, define deterministic ties, and backtrack original coordinates. A compressed value row discards those decisions. An empty-grid zero result must remain distinct from an actual coordinate witness.

Allow signed costs.

The right/down graph is still acyclic, so the DP proof remains valid even with negative costs. Update validation and prove a safe signed long bound. The Dijkstra verification oracle would no longer be valid for general negative edges and must be replaced with a DAG or exhaustive oracle.

Allow arbitrary moves or blocked cells.

Blocked cells need unreachable states with guarded addition and an explicit impossible-result contract. Four-direction movement creates cycles, invalidating the current evaluation order. With nonnegative costs a shortest-path method such as Dijkstra may be appropriate; negative cycles require separate semantics.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 124/20,000 characters

Self-review

I can define inclusive cell cost and initialize only real boundary routes.I can identify old up versus new left and justify exact long arithmetic.I can preserve aliased row objects and distinguish an empty-grid convention from a path.

Use the checklist to test your explanation. Checks apply to this visit.

Related foundations

Dynamic programming: state before recurrence

Keep practicing

Open focused practice

AceYourInterviews · 2026-10-17 · Original teaching content and implementations authored for AceYourInterviews. Familiar interview problem names describe standard algorithmic tasks; no company-frequency or platform-difficulty claims are made.