DSA-136 · Exact monotone-grid path counting with one-row compression

Unique Paths

Intermediate · Java 21 · Version 1 · editorial draft

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

Understand the problem

In a rows-by-columns rectangular grid, start at the upper-left cell and finish at the lower-right cell. Each move goes exactly one cell right or down. Return the number of distinct legal move sequences.

rows and columns are int values in 0..2000 inclusive. Negative or larger dimensions throw IllegalArgumentException. Validate both dimensions before accepting a zero-dimension result.
Return an exact BigInteger without a modulus. If either dimension is zero, return ZERO because there is no start-to-finish cell path. A 1×1 grid returns ONE: the empty move sequence already connects its single cell to itself.
There are no blocked cells, diagonal moves, or wraparound edges. Only the count is returned, not a list of paths. No caller-owned mutable input exists. The recursive baseline is restricted to small dimensions in verification.

Examples

Input: rows=3, columns=7
Output: 28
Every route has two down moves and six right moves, so choose the two down positions among eight moves.
Input: rows=2, columns=2
Output: 2
The routes are right-then-down and down-then-right.
Input: rows=1, columns=1
Output: 1
No move is needed; this is one complete route.
Input: rows=0, columns=4
Output: 0
A missing grid dimension means no cell path exists.

Before you start

Counting disjoint predecessor families
Grid dependency order and arbitrary-precision arithmetic

Recognize the structure

Every interior cell can be reached only from the cell above or immediately left. Removing the final move partitions its paths into two disjoint predecessor families. Many routes share those prefix counts, so caching cell answers removes repeated work. Because moves only increase coordinates, the grid is a DAG with a natural row-major evaluation order. A binomial coefficient is an independent alternative for this obstacle-free special case.

Try before revealing

Hint 1

Classify routes by their final right/down move.

Hint 2

What are the counts on the first row and column of a positive grid?

Hint 3

Keep one row, initialized to ONE, and add old up to new left from left to right.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Enumerate final-move predecessors recursively

For a positive rectangle, the destination has one route when either dimension is one; otherwise recurse on one fewer row and one fewer column and add the counts. A zero dimension is handled before recursion. The method revisits many smaller rectangles, with a safe O(2^(R+C)) upper bound on recursive arithmetic operations and O(R+C) live call depth. This is a teaching baseline, not a method to execute on 2000×2000. Tests compare small cases against a separately calculated exact binomial coefficient, and large cases exercise only the reference.

Improve the baseline

Define a cell count, including its boundary

P(r,c) counts paths from (0,0) to cell (r,c). P(0,0)=1 represents the empty move sequence. Every existing first-row and first-column cell also has exactly one route, since only straight movement is possible. A zero-size input is outside this cell table and returns zero by contract.

Add disjoint final-move families

For r,c>0, P(r,c)=P(r−1,c)+P(r,c−1). A path arriving from above ends in down, and a path arriving from the left ends in right, so no route belongs to both families. This is counting, not minimizing a route cost or checking reachability.

Fill a full table before compressing

For a 3×3 grid the conceptual rows are [1,1,1], [1,2,3], and [1,3,6]. Every dependency is finalized before its consumer in increasing row and column order. The boundary values are real counts, not uninitialized zeros or unreachable sentinels.

Retain only the live dependency frontier

Choose width=min(rows,columns) and height=max(rows,columns). Swapping axes bijectively swaps right/down routes, so it preserves the count. Initialize a BigInteger row to ONE. Before updating column c, dp[c] is old up and dp[c−1] is new left. Add and assign to dp[c]; column zero remains ONE.

Preserve exactness and distinguish operation count from bit cost

A 40×40 grid already has more paths than long can hold. BigInteger.add returns a fresh immutable value, so assigning its result is essential. An array filled with the same immutable ONE reference is safe. The row buffer saves table slots, but each count itself needs growing bits; constant-size integer arithmetic must not be assumed.

Why it is correct

Boundary correctness

A positive grid origin has exactly one empty path. A first-row or first-column cell can only be reached by the unique straight route. The initialized row and unchanged first column establish those bases.

Interior induction

Assume both predecessors are counted exactly. Every path into the current cell has a unique final right or down move; removing that move gives one predecessor path, and appending it reverses the correspondence. The families are disjoint and exhaustive, so addition gives the exact count.

Compression, symmetry, and termination

Row-major evaluation maintains old up at dp[c] and new left at dp[c−1]. Updating in that order preserves the conceptual table invariant. Swapping coordinate axes is a bijection of legal paths. Finite bounded loops finish with the destination count at the last buffer entry, and BigInteger avoids overflow.

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.math.BigInteger;
import java.util.Arrays;

public final class Solution {
    private Solution() {}
    private static void validate(int rows, int columns) {
        if (rows < 0 || columns < 0 || rows > 2_000 || columns > 2_000) throw new IllegalArgumentException("dimensions must be 0..2000");
    }
    public static BigInteger uniquePaths(int rows, int columns) {
        validate(rows, columns);
        if (rows == 0 || columns == 0) return BigInteger.ZERO;
        int width = Math.min(rows, columns), height = Math.max(rows, columns);
        BigInteger[] dp = new BigInteger[width];
        Arrays.fill(dp, BigInteger.ONE);
        for (int row = 1; row < height; row++) {
            for (int column = 1; column < width; column++) dp[column] = dp[column].add(dp[column - 1]);
        }
        return dp[width - 1];
    }
    // Baseline: enumerate final right/down moves. Small dimensions only.
    public static BigInteger baseline(int rows, int columns) {
        validate(rows, columns);
        if (rows == 0 || columns == 0) return BigInteger.ZERO;
        return paths(rows, columns);
    }
    private static BigInteger paths(int rows, int columns) {
        if (rows == 1 || columns == 1) return BigInteger.ONE;
        return paths(rows - 1, columns).add(paths(rows, columns - 1));
    }
}

Read the meaningful blocks

Validate both dimensions before empty handling

An input such as rows=0, columns=2001 must be rejected rather than hidden by a zero-row shortcut. Positive dimensions are required before a width-sized array is allocated.

Initialize the entire first row to ONE

This captures the one straight route to every first-row cell. It also handles width=1: the inner loop is empty and the one-column route remains unique.

Read old up and new left in place

dp[column].add(dp[column−1]) combines different row versions intentionally. Scanning columns backward would read old left and miss repeated rightward extensions. The full grid shown in the walkthrough is explanatory history, not a Java allocation.

Complexity

Let R,C be dimensions, W=min(R,C), H=max(R,C), and B the maximum count bit length (at least one). For positive dimensions the reference makes O(RC+1) BigInteger operations; with O(B)-cost addition, time is O((RC+1)B), and storage is O(W(B+1)) bits plus O(W) references. B=O(R+C), since there are at most 2^(R+C−2) move strings. Zero-dimension handling is O(1).

The recursive baseline has O(2^(R+C)) upper-bound arithmetic work and O((R+C)(B+1)) live storage including partial BigInteger values. A binomial formula can reduce arithmetic-operation count for this obstacle-free problem, but multiplication/division and intermediate bit lengths still need analysis. Returning all routes would require output-sensitive exponential work.

Exact-state walkthroughs

Reveal normal and boundary traces

Two predecessor families on a square

Input: {"rows":3,"columns":3} · Exact monotone path count: 6

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

Every existing first-row/column cell has one straight route. Axes may be swapped to minimize buffer width. Exact decimal strings preserve arbitrary-precision counts.

Unique Paths — exact right/down route families

Phase: initial.

Original dimensions: 3 rows × 3 columns. The equivalent counting grid below uses height=3, width=3; swapping axes bijectively swaps right and down moves.

Conceptual path counts — · means uncomputed
Row / column	0	1	2
0	1	1	1
1	1	·	·
2	1	·	·

Actual one-row Java buffer

0: 1
1: 1
2: 1

Every existing first-row/column cell has one straight route. Interior sums combine disjoint final-move families. The 1×1 origin has one empty route. 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	`{"rows":3,"columns":3}`
phase	`"initial"`
height	`3`
width	`3`
table	`[["1","1","1"],["1",null,null],["1",null,null]]`
dp	`["1","1","1"]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 
 4 public final class Solution {
 5     private Solution() {}
 6     private static void validate(int rows, int columns) {
 7         if (rows < 0 || columns < 0 || rows > 2_000 || columns > 2_000) throw new IllegalArgumentException("dimensions must be 0..2000");
 8     }
 9     public static BigInteger uniquePaths(int rows, int columns) {
10         validate(rows, columns);
11         if (rows == 0 || columns == 0) return BigInteger.ZERO;
12         int width = Math.min(rows, columns), height = Math.max(rows, columns);
13         BigInteger[] dp = new BigInteger[width];
14         Arrays.fill(dp, BigInteger.ONE);
15         for (int row = 1; row < height; row++) {
16             for (int column = 1; column < width; column++) dp[column] = dp[column].add(dp[column - 1]);
17         }
18         return dp[width - 1];
19     }
20     // Baseline: enumerate final right/down moves. Small dimensions only.
21     public static BigInteger baseline(int rows, int columns) {
22         validate(rows, columns);
23         if (rows == 0 || columns == 0) return BigInteger.ZERO;
24         return paths(rows, columns);
25     }
26     private static BigInteger paths(int rows, int columns) {
27         if (rows == 1 || columns == 1) return BigInteger.ONE;
28         return paths(rows - 1, columns).add(paths(rows, columns - 1));
29     }
30 }
31

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.
Every existing first-row/column cell has one straight route. Axes may be swapped to minimize buffer width. Exact decimal strings preserve arbitrary-precision counts.
input
{"rows":3,"columns":3}
phase
"initial"
height
3
width
3
table
[["1","1","1"],["1",null,null],["1",null,null]]
dp
["1","1","1"]
The first-column count stays one for this new row.
At the start of a row, all other buffer entries still describe the preceding row. Column zero is a known straight-route base.
input
{"rows":3,"columns":3}
phase
"row-start"
height
3
width
3
table
[["1","1","1"],["1",null,null],["1",null,null]]
dp
["1","1","1"]
row
1
column
0
Read the incoming finalized dependencies before writing this cell.
The predecessor families have different final moves and are disjoint. dp[column] is old up; dp[column−1] is new left.
input
{"rows":3,"columns":3}
phase
"candidate"
height
3
width
3
table
[["1","1","1"],["1",null,null],["1",null,null]]
dp
["1","1","1"]
row
1
column
1
up
"1"
left
"1"
cost
null
next
"2"
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
{"rows":3,"columns":3}
phase
"commit"
height
3
width
3
table
[["1","1","1"],["1","2",null],["1",null,null]]
dp
["1","2","1"]
row
1
column
1
up
"1"
left
"1"
cost
null
next
"2"
firstRow
false
Read the incoming finalized dependencies before writing this cell.
The predecessor families have different final moves and are disjoint. dp[column] is old up; dp[column−1] is new left.
input
{"rows":3,"columns":3}
phase
"candidate"
height
3
width
3
table
[["1","1","1"],["1","2",null],["1",null,null]]
dp
["1","2","1"]
row
1
column
2
up
"1"
left
"2"
cost
null
next
"3"
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
{"rows":3,"columns":3}
phase
"commit"
height
3
width
3
table
[["1","1","1"],["1","2","3"],["1",null,null]]
dp
["1","2","3"]
row
1
column
2
up
"1"
left
"2"
cost
null
next
"3"
firstRow
false
The first-column count stays one for this new row.
At the start of a row, all other buffer entries still describe the preceding row. Column zero is a known straight-route base.
input
{"rows":3,"columns":3}
phase
"row-start"
height
3
width
3
table
[["1","1","1"],["1","2","3"],["1",null,null]]
dp
["1","2","3"]
row
2
column
0
Read the incoming finalized dependencies before writing this cell.
The predecessor families have different final moves and are disjoint. dp[column] is old up; dp[column−1] is new left.
input
{"rows":3,"columns":3}
phase
"candidate"
height
3
width
3
table
[["1","1","1"],["1","2","3"],["1",null,null]]
dp
["1","2","3"]
row
2
column
1
up
"2"
left
"1"
cost
null
next
"3"
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
{"rows":3,"columns":3}
phase
"commit"
height
3
width
3
table
[["1","1","1"],["1","2","3"],["1","3",null]]
dp
["1","3","3"]
row
2
column
1
up
"2"
left
"1"
cost
null
next
"3"
firstRow
false
Read the incoming finalized dependencies before writing this cell.
The predecessor families have different final moves and are disjoint. dp[column] is old up; dp[column−1] is new left.
input
{"rows":3,"columns":3}
phase
"candidate"
height
3
width
3
table
[["1","1","1"],["1","2","3"],["1","3",null]]
dp
["1","3","3"]
row
2
column
2
up
"3"
left
"3"
cost
null
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
{"rows":3,"columns":3}
phase
"commit"
height
3
width
3
table
[["1","1","1"],["1","2","3"],["1","3","6"]]
dp
["1","3","6"]
row
2
column
2
up
"3"
left
"3"
cost
null
next
"6"
firstRow
false
Return the destination value from the final row.
Counting returns the exact number of monotone routes; one cell contributes one empty move sequence.
input
{"rows":3,"columns":3}
phase
"complete"
height
3
width
3
table
[["1","1","1"],["1","2","3"],["1","3","6"]]
dp
["1","3","6"]
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
"6"

Shorter axis becomes the buffer

Input: {"rows":2,"columns":4} · Exact monotone path count: 4

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

Every existing first-row/column cell has one straight route. Axes may be swapped to minimize buffer width. Exact decimal strings preserve arbitrary-precision counts.

Unique Paths — exact right/down route families

Phase: initial.

Original dimensions: 2 rows × 4 columns. The equivalent counting grid below uses height=4, width=2; swapping axes bijectively swaps right and down moves.

Conceptual path counts — · means uncomputed
Row / column	0	1
0	1	1
1	1	·
2	1	·
3	1	·

Actual one-row Java buffer

0: 1
1: 1

State after this step
Variable	Value
input	`{"rows":2,"columns":4}`
phase	`"initial"`
height	`4`
width	`2`
table	`[["1","1"],["1",null],["1",null],["1",null]]`
dp	`["1","1"]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 
 4 public final class Solution {
 5     private Solution() {}
 6     private static void validate(int rows, int columns) {
 7         if (rows < 0 || columns < 0 || rows > 2_000 || columns > 2_000) throw new IllegalArgumentException("dimensions must be 0..2000");
 8     }
 9     public static BigInteger uniquePaths(int rows, int columns) {
10         validate(rows, columns);
11         if (rows == 0 || columns == 0) return BigInteger.ZERO;
12         int width = Math.min(rows, columns), height = Math.max(rows, columns);
13         BigInteger[] dp = new BigInteger[width];
14         Arrays.fill(dp, BigInteger.ONE);
15         for (int row = 1; row < height; row++) {
16             for (int column = 1; column < width; column++) dp[column] = dp[column].add(dp[column - 1]);
17         }
18         return dp[width - 1];
19     }
20     // Baseline: enumerate final right/down moves. Small dimensions only.
21     public static BigInteger baseline(int rows, int columns) {
22         validate(rows, columns);
23         if (rows == 0 || columns == 0) return BigInteger.ZERO;
24         return paths(rows, columns);
25     }
26     private static BigInteger paths(int rows, int columns) {
27         if (rows == 1 || columns == 1) return BigInteger.ONE;
28         return paths(rows - 1, columns).add(paths(rows, columns - 1));
29     }
30 }
31

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.
Every existing first-row/column cell has one straight route. Axes may be swapped to minimize buffer width. Exact decimal strings preserve arbitrary-precision counts.
input
{"rows":2,"columns":4}
phase
"initial"
height
4
width
2
table
[["1","1"],["1",null],["1",null],["1",null]]
dp
["1","1"]
The first-column count stays one for this new row.
At the start of a row, all other buffer entries still describe the preceding row. Column zero is a known straight-route base.
input
{"rows":2,"columns":4}
phase
"row-start"
height
4
width
2
table
[["1","1"],["1",null],["1",null],["1",null]]
dp
["1","1"]
row
1
column
0
Read the incoming finalized dependencies before writing this cell.
The predecessor families have different final moves and are disjoint. dp[column] is old up; dp[column−1] is new left.
input
{"rows":2,"columns":4}
phase
"candidate"
height
4
width
2
table
[["1","1"],["1",null],["1",null],["1",null]]
dp
["1","1"]
row
1
column
1
up
"1"
left
"1"
cost
null
next
"2"
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
{"rows":2,"columns":4}
phase
"commit"
height
4
width
2
table
[["1","1"],["1","2"],["1",null],["1",null]]
dp
["1","2"]
row
1
column
1
up
"1"
left
"1"
cost
null
next
"2"
firstRow
false
The first-column count stays one for this new row.
At the start of a row, all other buffer entries still describe the preceding row. Column zero is a known straight-route base.
input
{"rows":2,"columns":4}
phase
"row-start"
height
4
width
2
table
[["1","1"],["1","2"],["1",null],["1",null]]
dp
["1","2"]
row
2
column
0
Read the incoming finalized dependencies before writing this cell.
The predecessor families have different final moves and are disjoint. dp[column] is old up; dp[column−1] is new left.
input
{"rows":2,"columns":4}
phase
"candidate"
height
4
width
2
table
[["1","1"],["1","2"],["1",null],["1",null]]
dp
["1","2"]
row
2
column
1
up
"2"
left
"1"
cost
null
next
"3"
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
{"rows":2,"columns":4}
phase
"commit"
height
4
width
2
table
[["1","1"],["1","2"],["1","3"],["1",null]]
dp
["1","3"]
row
2
column
1
up
"2"
left
"1"
cost
null
next
"3"
firstRow
false
The first-column count stays one for this new row.
At the start of a row, all other buffer entries still describe the preceding row. Column zero is a known straight-route base.
input
{"rows":2,"columns":4}
phase
"row-start"
height
4
width
2
table
[["1","1"],["1","2"],["1","3"],["1",null]]
dp
["1","3"]
row
3
column
0
Read the incoming finalized dependencies before writing this cell.
The predecessor families have different final moves and are disjoint. dp[column] is old up; dp[column−1] is new left.
input
{"rows":2,"columns":4}
phase
"candidate"
height
4
width
2
table
[["1","1"],["1","2"],["1","3"],["1",null]]
dp
["1","3"]
row
3
column
1
up
"3"
left
"1"
cost
null
next
"4"
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
{"rows":2,"columns":4}
phase
"commit"
height
4
width
2
table
[["1","1"],["1","2"],["1","3"],["1","4"]]
dp
["1","4"]
row
3
column
1
up
"3"
left
"1"
cost
null
next
"4"
firstRow
false
Return the destination value from the final row.
Counting returns the exact number of monotone routes; one cell contributes one empty move sequence.
input
{"rows":2,"columns":4}
phase
"complete"
height
4
width
2
table
[["1","1"],["1","2"],["1","3"],["1","4"]]
dp
["1","4"]
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
"4"

One cell has one empty route

Input: {"rows":1,"columns":1} · Exact monotone path count: 1

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

Every existing first-row/column cell has one straight route. Axes may be swapped to minimize buffer width. Exact decimal strings preserve arbitrary-precision counts.

Unique Paths — exact right/down route families

Phase: initial.

Original dimensions: 1 rows × 1 columns. The equivalent counting grid below uses height=1, width=1; swapping axes bijectively swaps right and down moves.

Conceptual path counts — · means uncomputed
Row / column	0
0	1

Actual one-row Java buffer

0: 1

State after this step
Variable	Value
input	`{"rows":1,"columns":1}`
phase	`"initial"`
height	`1`
width	`1`
table	`[["1"]]`
dp	`["1"]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 
 4 public final class Solution {
 5     private Solution() {}
 6     private static void validate(int rows, int columns) {
 7         if (rows < 0 || columns < 0 || rows > 2_000 || columns > 2_000) throw new IllegalArgumentException("dimensions must be 0..2000");
 8     }
 9     public static BigInteger uniquePaths(int rows, int columns) {
10         validate(rows, columns);
11         if (rows == 0 || columns == 0) return BigInteger.ZERO;
12         int width = Math.min(rows, columns), height = Math.max(rows, columns);
13         BigInteger[] dp = new BigInteger[width];
14         Arrays.fill(dp, BigInteger.ONE);
15         for (int row = 1; row < height; row++) {
16             for (int column = 1; column < width; column++) dp[column] = dp[column].add(dp[column - 1]);
17         }
18         return dp[width - 1];
19     }
20     // Baseline: enumerate final right/down moves. Small dimensions only.
21     public static BigInteger baseline(int rows, int columns) {
22         validate(rows, columns);
23         if (rows == 0 || columns == 0) return BigInteger.ZERO;
24         return paths(rows, columns);
25     }
26     private static BigInteger paths(int rows, int columns) {
27         if (rows == 1 || columns == 1) return BigInteger.ONE;
28         return paths(rows - 1, columns).add(paths(rows, columns - 1));
29     }
30 }
31

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.
Every existing first-row/column cell has one straight route. Axes may be swapped to minimize buffer width. Exact decimal strings preserve arbitrary-precision counts.
input
{"rows":1,"columns":1}
phase
"initial"
height
1
width
1
table
[["1"]]
dp
["1"]
Return the destination value from the final row.
Counting returns the exact number of monotone routes; one cell contributes one empty move sequence.
input
{"rows":1,"columns":1}
phase
"complete"
height
1
width
1
table
[["1"]]
dp
["1"]
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
"1"

A zero dimension has no cell path

Input: {"rows":0,"columns":3} · Exact monotone path count: 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.

Unique Paths — exact right/down route families

Phase: empty.

Original dimensions: 0 rows × 3 columns. The equivalent counting grid below uses height=3, width=0; swapping axes bijectively swaps right and down moves.

No cell path exists when a dimension is zero; return exact zero. Validation has already completed; no buffer is allocated.

State after this step
Variable	Value
input	`{"rows":0,"columns":3}`
phase	`"empty"`
height	`3`
width	`0`
table	`[]`
dp	`[]`

See the affected Java block

 1 import java.math.BigInteger;
 2 import java.util.Arrays;
 3 
 4 public final class Solution {
 5     private Solution() {}
 6     private static void validate(int rows, int columns) {
 7         if (rows < 0 || columns < 0 || rows > 2_000 || columns > 2_000) throw new IllegalArgumentException("dimensions must be 0..2000");
 8     }
 9     public static BigInteger uniquePaths(int rows, int columns) {
10         validate(rows, columns);
11         if (rows == 0 || columns == 0) return BigInteger.ZERO;
12         int width = Math.min(rows, columns), height = Math.max(rows, columns);
13         BigInteger[] dp = new BigInteger[width];
14         Arrays.fill(dp, BigInteger.ONE);
15         for (int row = 1; row < height; row++) {
16             for (int column = 1; column < width; column++) dp[column] = dp[column].add(dp[column - 1]);
17         }
18         return dp[width - 1];
19     }
20     // Baseline: enumerate final right/down moves. Small dimensions only.
21     public static BigInteger baseline(int rows, int columns) {
22         validate(rows, columns);
23         if (rows == 0 || columns == 0) return BigInteger.ZERO;
24         return paths(rows, columns);
25     }
26     private static BigInteger paths(int rows, int columns) {
27         if (rows == 1 || columns == 1) return BigInteger.ONE;
28         return paths(rows - 1, columns).add(paths(rows, columns - 1));
29     }
30 }
31

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
{"rows":0,"columns":3}
phase
"empty"
height
3
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: rows=1, columns=8
Output: 1
Only a straight horizontal route.
Input: rows=8, columns=1
Output: 1
Symmetric vertical case.
Input: rows=3, columns=3
Output: 6
Multiple predecessor layers.
Input: rows=2, columns=3
Output: 3
Axis swapping preserves the answer.
Input: rows=-1, columns=1
Output: IllegalArgumentException
Negative dimension.
Input: rows=0, columns=2001
Output: IllegalArgumentException
Validate both dimensions before the zero shortcut.

Common mistakes and counterexamples

Seed the origin with zero

Counterexample: A 1×1 grid would have no route, and all later counts would vanish.

Use one empty route at an existing origin.

Treat zero dimensions like a one-cell grid

Counterexample: 0×4 contains no origin-to-target cell path.

Handle a missing dimension separately from the positive-grid base.

Scan the compressed row backward

Counterexample: A 3×3 row would read a stale left predecessor and undercount.

Visit columns left-to-right so left belongs to the current row.

Use long or discard BigInteger.add

Counterexample: 40×40 exceeds long; add does not mutate its receiver.

Assign exact BigInteger sums and expose bit costs.

Follow-ups

Add blocked cells.

A blocked cell has count zero, including a blocked origin or destination. Keep the same predecessor sum for open cells, but initialize boundaries through the obstacle rule rather than filling them blindly with ONE. The binomial shortcut no longer applies.

Return the kth route in a deterministic order.

Compute exact suffix route counts, compare k with the block of routes beginning with the first allowed move, and subtract blocks while descending. Specify zero- or one-based k, bounds, and move order. A total count alone does not encode the necessary suffix decisions.

Use a binomial coefficient instead of DP.

A route contains R−1 down and C−1 right moves, so choose(R+C−2,R−1). Multiply and divide with BigInteger while maintaining exact binomial identities, and choose the smaller selection count. This independent derivation relies on an obstacle-free rectangle.

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 · 147/20,000 characters

Self-review

I can derive disjoint last-move counting and the one-empty-route base.I can state old up versus new left in the compressed row and justify axis swapping.I can distinguish arithmetic-operation counts from BigInteger bit complexity.

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.