DSA-108 · FOCUSED PRACTICE
Longest Increasing Path in a Matrix
Advanced · Java 21 · Version 1 · editorial draft
Java reference and baseline verified on JDK 21: 44622 deterministic checks. Learner drafts are not executed.
Understand the problem
Return the maximum number of cells in an orthogonally adjacent path with strictly increasing values. Return zero for a matrix with no cells.
- matrix is a nonnull rectangular int array with nonnull rows. At most 100,000 rows and 100,000 cells are size preconditions. Null outer input throws NullPointerException; null/ragged rows throw IllegalArgumentException before traversal. Empty and zero-column matrices are allowed.
- Only up/right/down/left moves are allowed, and every next value must be strictly greater. Equal values and diagonals are not edges. Heights span the full int domain; use direct comparisons instead of subtracting. Length counts cells, so an isolated cell or nonempty plateau returns one.
- Preserve every source value and row reference. Shared row objects are valid because coordinates define vertices and the algorithm is read-only. Return only the maximum length; the main implementation allocates degree/queue state rather than mutating heights or relying on recursive depth.
Examples
Input:
[[9,9,4],[6,6,8],[2,1,1]]
Output:4One path is 1→2→6→9. Two 9 cells are separate maxima; equal heights do not extend a path.
Input:
[[MIN,0,MAX]]
Output:3Both direct inequalities are valid without overflowing subtraction.
Input:
[[7,7],[7,7]]
Output:1No strict edge exists, although all four cells are orthogonally connected.
Input:
[[],[]]
Output:0Row validation still costs work, but there are no path vertices.
Before you start
- Implicit grid adjacency and strict-order acyclicity
- Longest-path DAG recurrence and frozen reverse layers
Recognize the structure
Longest path is hard in arbitrary directed graphs, but strict value increase forbids cycles: a closed walk would require a value to be greater than itself. Treat each cell as a DAG vertex, orient edges to greater orthogonal neighbors, and evaluate longest suffixes from sinks backward.
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.
No unsaved text changes · 161/20,000 characters
Self-review
Use the checklist to test your explanation. Checks apply to this visit.
Try before revealing
Hint 1
Orient each orthogonal edge from a lower value to a strictly higher one.
Hint 2
Strict increase makes a DAG, so compute longest suffixes from its maxima.
Hint 3
Count greater successors, remove zero-degree maxima in frozen batches, and release lower predecessors.
Derive the solution
Reveal the baseline, optimized reasoning, and Java code
Enumerate every increasing continuation without memoization
Start a recursive search from every cell. The returned local value is one plus the best greater-neighbor continuation, or one if none exists. No path-local visited set is needed because strict increase prevents revisiting a coordinate. Shared suffixes are recomputed, making this compiling baseline potentially exponential and unsafe for long recursion depths; use it only on small verification matrices.
Improve the baseline
Count each cell’s greater successors
For each coordinate inspect four directions and count strictly greater neighbors. Local maxima have no outgoing edges and seed the first reverse layer.
Peel backward in complete batches
Remove exactly the captured queue size for a layer. For each lower neighbor, decrement its remaining-greater count; zero releases it into a later layer. Equality performs no decrement.
Read longest length from the number of layers
A cell becomes available only after all greater successors are removed. Its layer is one plus the maximum successor layer. Counting all layers therefore gives the longest increasing path’s number of cells, without storing an individual path.
Why it is correct
Strict-order DAG
Every directed edge raises the value, so a cycle would imply value[v]<value[v]. Thus every nonempty residual graph has a sink and all cells are eventually removed.
Suffix recurrence
Define L(v)=1 for a sink and 1+max(L(successor)) otherwise. Each legal path takes a first greater successor, giving the upper bound; choosing a maximizing successor constructs a path attaining it.
Frozen layers realize the recurrence
All sinks occupy layer one. A predecessor becomes ready when its final greater successor is discharged, so it enters the next layer after the greatest successor layer. Captured sizes prevent newly ready predecessors from collapsing into the current layer. The maximum layer is max L(v), not a shortest distance from one chosen source.
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.*;
public final class Solution {
private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}};
private static int validate(int[][] matrix) {
Objects.requireNonNull(matrix,"matrix");int columns=matrix.length==0?0:matrix[0]==null?-1:matrix[0].length;for(int[] row:matrix)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular matrix");return columns;
}
public static int longestPath(int[][] matrix) {
int columns=validate(matrix);int[][] remaining=new int[matrix.length][columns];ArrayDeque<int[]> ready=new ArrayDeque<>();
for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++) {
for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])remaining[r][c]++;}
if(remaining[r][c]==0)ready.addLast(new int[]{r,c});
}
int layers=0;
while(!ready.isEmpty()) {
int size=ready.size();layers++;
for(int i=0;i<size;i++) {
int[] cell=ready.removeFirst();
for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]<matrix[cell[0]][cell[1]]&&--remaining[nr][nc]==0)ready.addLast(new int[]{nr,nc});}
}
}
return layers;
}
public static int baseline(int[][] matrix) {
int columns=validate(matrix),best=0;for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++)best=Math.max(best,enumerate(matrix,columns,r,c));return best;
}
private static int enumerate(int[][] matrix,int columns,int r,int c) {
int best=1;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])best=Math.max(best,1+enumerate(matrix,columns,nr,nc));}return best;
}
}
Read the meaningful blocks
Remaining degrees refer to greater neighbors
The main queue starts at maxima, not minima. On removing a high cell, discharge only lower orthogonal neighbors; using <= would introduce plateau cycles or invalid longer paths.
The current cell can have pending discharge work
Walkthrough removal history records the pop before its reverse edges are all processed. Remaining counts in such intermediate states include pending occurrences from that current cell. The stable recurrence applies at completed layer boundaries.
No cell values are temporary marks
Degrees live in a separate matrix, making aliased read-only rows safe. Direct < and > comparisons handle MIN/MAX. Frozen size and scalar layers avoid a deep recursive stack.
Complexity
Let R be rows, B cells, and N=R+B. Main time is O(N+1): two four-neighbor inspections per cell plus shape validation and layer processing. Auxiliary degree rows and queue require O(N+1) storage; output is one int. R remains visible when rows have zero columns.
A loose baseline bound is O(R+(B+1)·4^B) time from branching path enumeration, with O(B+1) recursive stack space. Strict increase bounds a path by B, but does not prevent exponentially many different paths or repeated suffix work. The baseline is tested only on small inputs; the main method handles a 100,000-cell increasing corridor iteratively.
Exact-state walkthroughs
Reveal normal and boundary traces
Reverse layers evaluate shared increasing suffixes
Input: [[9,9,4],[6,6,8],[2,1,1]] · Longest strict path in cells: 4
Step 1 of 25: Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
Phase: seed.
Unchanged heights — ✓ removed coordinate
Remaining strictly greater successor occurrences — ✓ already removed
Coordinate FIFO — front at left
- (0, 0)
- (0, 1)
- (1, 2)
Layer number: 0. Pops remaining in the frozen current layer: 0.
Removed coordinates — teaching history
Empty.
Strict increases define the DAG; equal heights have no edge. A lower cell waits for every greater successor, so reverse layers measure the longest suffix, not a shortest route. Zero counts can belong to queued or already removed cells. The current pop may still have pending reverse edges to discharge before the next layer starts.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| matrix | [[9,9,4],[6,6,8],[2,1,1]] |
| remaining | [[0,0,2],[1,2,0],[1,2,1]] |
| ready | [[0,0],[0,1],[1,2]] |
| processed | [] |
| layers | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] matrix) { 5 Objects.requireNonNull(matrix,"matrix");int columns=matrix.length==0?0:matrix[0]==null?-1:matrix[0].length;for(int[] row:matrix)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular matrix");return columns; 6 } 7 public static int longestPath(int[][] matrix) { 8 int columns=validate(matrix);int[][] remaining=new int[matrix.length][columns];ArrayDeque<int[]> ready=new ArrayDeque<>(); 9 for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++) { 10 for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])remaining[r][c]++;} 11 if(remaining[r][c]==0)ready.addLast(new int[]{r,c}); 12 } 13 int layers=0; 14 while(!ready.isEmpty()) { 15 int size=ready.size();layers++; 16 for(int i=0;i<size;i++) { 17 int[] cell=ready.removeFirst(); 18 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]<matrix[cell[0]][cell[1]]&&--remaining[nr][nc]==0)ready.addLast(new int[]{nr,nc});} 19 } 20 } 21 return layers; 22 } 23 public static int baseline(int[][] matrix) { 24 int columns=validate(matrix),best=0;for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++)best=Math.max(best,enumerate(matrix,columns,r,c));return best; 25 } 26 private static int enumerate(int[][] matrix,int columns,int r,int c) { 27 int best=1;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])best=Math.max(best,1+enumerate(matrix,columns,nr,nc));}return best; 28 } 29 } 30
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,2],[1,2,0],[1,2,1]]- ready
[[0,0],[0,1],[1,2]]- processed
[]- layers
0- leftInLayer
0- current
null- phase
"seed"
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,2],[1,2,0],[1,2,1]]- ready
[[0,0],[0,1],[1,2]]- processed
[]- layers
1- leftInLayer
3- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,2],[1,2,0],[1,2,1]]- ready
[[0,1],[1,2]]- processed
[[0,0]]- layers
1- leftInLayer
2- current
[0,0]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,2],[0,2,0],[1,2,1]]- ready
[[0,1],[1,2],[1,0]]- processed
[[0,0]]- layers
1- leftInLayer
2- current
[0,0]- phase
"release"- predecessor
[1,0]
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,2],[0,2,0],[1,2,1]]- ready
[[1,2],[1,0]]- processed
[[0,0],[0,1]]- layers
1- leftInLayer
1- current
[0,1]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,1],[0,2,0],[1,2,1]]- ready
[[1,2],[1,0]]- processed
[[0,0],[0,1]]- layers
1- leftInLayer
1- current
[0,1]- phase
"release"- predecessor
[0,2]
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,1],[0,1,0],[1,2,1]]- ready
[[1,2],[1,0]]- processed
[[0,0],[0,1]]- layers
1- leftInLayer
1- current
[0,1]- phase
"release"- predecessor
[1,1]
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,1],[0,1,0],[1,2,1]]- ready
[[1,0]]- processed
[[0,0],[0,1],[1,2]]- layers
1- leftInLayer
0- current
[1,2]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,1,0],[1,2,1]]- ready
[[1,0],[0,2]]- processed
[[0,0],[0,1],[1,2]]- layers
1- leftInLayer
0- current
[1,2]- phase
"release"- predecessor
[0,2]
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,1,0],[1,2,0]]- ready
[[1,0],[0,2],[2,2]]- processed
[[0,0],[0,1],[1,2]]- layers
1- leftInLayer
0- current
[1,2]- phase
"release"- predecessor
[2,2]
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[1,2,0]]- ready
[[1,0],[0,2],[2,2],[1,1]]- processed
[[0,0],[0,1],[1,2]]- layers
1- leftInLayer
0- current
[1,2]- phase
"release"- predecessor
[1,1]
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[1,2,0]]- ready
[[1,0],[0,2],[2,2],[1,1]]- processed
[[0,0],[0,1],[1,2]]- layers
2- leftInLayer
4- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[1,2,0]]- ready
[[0,2],[2,2],[1,1]]- processed
[[0,0],[0,1],[1,2],[1,0]]- layers
2- leftInLayer
3- current
[1,0]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,2,0]]- ready
[[0,2],[2,2],[1,1],[2,0]]- processed
[[0,0],[0,1],[1,2],[1,0]]- layers
2- leftInLayer
3- current
[1,0]- phase
"release"- predecessor
[2,0]
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,2,0]]- ready
[[2,2],[1,1],[2,0]]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2]]- layers
2- leftInLayer
2- current
[0,2]- phase
"remove"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,2,0]]- ready
[[1,1],[2,0]]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2]]- layers
2- leftInLayer
1- current
[2,2]- phase
"remove"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,2,0]]- ready
[[2,0]]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1]]- layers
2- leftInLayer
0- current
[1,1]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,1,0]]- ready
[[2,0]]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1]]- layers
2- leftInLayer
0- current
[1,1]- phase
"release"- predecessor
[2,1]
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,1,0]]- ready
[[2,0]]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1]]- layers
3- leftInLayer
1- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,1,0]]- ready
[]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1],[2,0]]- layers
3- leftInLayer
0- current
[2,0]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,0,0]]- ready
[[2,1]]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1],[2,0]]- layers
3- leftInLayer
0- current
[2,0]- phase
"release"- predecessor
[2,1]
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,0,0]]- ready
[[2,1]]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1],[2,0]]- layers
4- leftInLayer
1- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,0,0]]- ready
[]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1],[2,0],[2,1]]- layers
4- leftInLayer
0- current
[2,1]- phase
"remove"
- All cells are peeled; the number of layers is the longest cell count.
A nonempty strict-increase DAG always has a sink. Empty/zero-column matrices have no vertices and return zero.
- matrix
[[9,9,4],[6,6,8],[2,1,1]]- remaining
[[0,0,0],[0,0,0],[0,0,0]]- ready
[]- processed
[[0,0],[0,1],[1,2],[1,0],[0,2],[2,2],[1,1],[2,0],[2,1]]- layers
4- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
4
Equal values create no path edges
Input: [[7,7],[7,7]] · Longest strict path in cells: 1
Step 1 of 8: Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
Phase: seed.
Unchanged heights — ✓ removed coordinate
Remaining strictly greater successor occurrences — ✓ already removed
Coordinate FIFO — front at left
- (0, 0)
- (0, 1)
- (1, 0)
- (1, 1)
Layer number: 0. Pops remaining in the frozen current layer: 0.
Removed coordinates — teaching history
Empty.
Strict increases define the DAG; equal heights have no edge. A lower cell waits for every greater successor, so reverse layers measure the longest suffix, not a shortest route. Zero counts can belong to queued or already removed cells. The current pop may still have pending reverse edges to discharge before the next layer starts.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| matrix | [[7,7],[7,7]] |
| remaining | [[0,0],[0,0]] |
| ready | [[0,0],[0,1],[1,0],[1,1]] |
| processed | [] |
| layers | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] matrix) { 5 Objects.requireNonNull(matrix,"matrix");int columns=matrix.length==0?0:matrix[0]==null?-1:matrix[0].length;for(int[] row:matrix)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular matrix");return columns; 6 } 7 public static int longestPath(int[][] matrix) { 8 int columns=validate(matrix);int[][] remaining=new int[matrix.length][columns];ArrayDeque<int[]> ready=new ArrayDeque<>(); 9 for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++) { 10 for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])remaining[r][c]++;} 11 if(remaining[r][c]==0)ready.addLast(new int[]{r,c}); 12 } 13 int layers=0; 14 while(!ready.isEmpty()) { 15 int size=ready.size();layers++; 16 for(int i=0;i<size;i++) { 17 int[] cell=ready.removeFirst(); 18 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]<matrix[cell[0]][cell[1]]&&--remaining[nr][nc]==0)ready.addLast(new int[]{nr,nc});} 19 } 20 } 21 return layers; 22 } 23 public static int baseline(int[][] matrix) { 24 int columns=validate(matrix),best=0;for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++)best=Math.max(best,enumerate(matrix,columns,r,c));return best; 25 } 26 private static int enumerate(int[][] matrix,int columns,int r,int c) { 27 int best=1;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])best=Math.max(best,1+enumerate(matrix,columns,nr,nc));}return best; 28 } 29 } 30
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
- matrix
[[7,7],[7,7]]- remaining
[[0,0],[0,0]]- ready
[[0,0],[0,1],[1,0],[1,1]]- processed
[]- layers
0- leftInLayer
0- current
null- phase
"seed"
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[7,7],[7,7]]- remaining
[[0,0],[0,0]]- ready
[[0,0],[0,1],[1,0],[1,1]]- processed
[]- layers
1- leftInLayer
4- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[7,7],[7,7]]- remaining
[[0,0],[0,0]]- ready
[[0,1],[1,0],[1,1]]- processed
[[0,0]]- layers
1- leftInLayer
3- current
[0,0]- phase
"remove"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[7,7],[7,7]]- remaining
[[0,0],[0,0]]- ready
[[1,0],[1,1]]- processed
[[0,0],[0,1]]- layers
1- leftInLayer
2- current
[0,1]- phase
"remove"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[7,7],[7,7]]- remaining
[[0,0],[0,0]]- ready
[[1,1]]- processed
[[0,0],[0,1],[1,0]]- layers
1- leftInLayer
1- current
[1,0]- phase
"remove"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[7,7],[7,7]]- remaining
[[0,0],[0,0]]- ready
[]- processed
[[0,0],[0,1],[1,0],[1,1]]- layers
1- leftInLayer
0- current
[1,1]- phase
"remove"
- All cells are peeled; the number of layers is the longest cell count.
A nonempty strict-increase DAG always has a sink. Empty/zero-column matrices have no vertices and return zero.
- matrix
[[7,7],[7,7]]- remaining
[[0,0],[0,0]]- ready
[]- processed
[[0,0],[0,1],[1,0],[1,1]]- layers
1- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
1
Direct inequalities across int extremes
Input: [[-2147483648,0,2147483647]] · Longest strict path in cells: 3
Step 1 of 11: Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
Phase: seed.
Unchanged heights — ✓ removed coordinate
MIN = −2,147,483,648; MAX = 2,147,483,647. Compare values directly.
Remaining strictly greater successor occurrences — ✓ already removed
Coordinate FIFO — front at left
- (0, 2)
Layer number: 0. Pops remaining in the frozen current layer: 0.
Removed coordinates — teaching history
Empty.
Strict increases define the DAG; equal heights have no edge. A lower cell waits for every greater successor, so reverse layers measure the longest suffix, not a shortest route. Zero counts can belong to queued or already removed cells. The current pop may still have pending reverse edges to discharge before the next layer starts.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| matrix | [[-2147483648,0,2147483647]] |
| remaining | [[1,1,0]] |
| ready | [[0,2]] |
| processed | [] |
| layers | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] matrix) { 5 Objects.requireNonNull(matrix,"matrix");int columns=matrix.length==0?0:matrix[0]==null?-1:matrix[0].length;for(int[] row:matrix)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular matrix");return columns; 6 } 7 public static int longestPath(int[][] matrix) { 8 int columns=validate(matrix);int[][] remaining=new int[matrix.length][columns];ArrayDeque<int[]> ready=new ArrayDeque<>(); 9 for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++) { 10 for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])remaining[r][c]++;} 11 if(remaining[r][c]==0)ready.addLast(new int[]{r,c}); 12 } 13 int layers=0; 14 while(!ready.isEmpty()) { 15 int size=ready.size();layers++; 16 for(int i=0;i<size;i++) { 17 int[] cell=ready.removeFirst(); 18 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]<matrix[cell[0]][cell[1]]&&--remaining[nr][nc]==0)ready.addLast(new int[]{nr,nc});} 19 } 20 } 21 return layers; 22 } 23 public static int baseline(int[][] matrix) { 24 int columns=validate(matrix),best=0;for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++)best=Math.max(best,enumerate(matrix,columns,r,c));return best; 25 } 26 private static int enumerate(int[][] matrix,int columns,int r,int c) { 27 int best=1;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])best=Math.max(best,1+enumerate(matrix,columns,nr,nc));}return best; 28 } 29 } 30
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[1,1,0]]- ready
[[0,2]]- processed
[]- layers
0- leftInLayer
0- current
null- phase
"seed"
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[1,1,0]]- ready
[[0,2]]- processed
[]- layers
1- leftInLayer
1- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[1,1,0]]- ready
[]- processed
[[0,2]]- layers
1- leftInLayer
0- current
[0,2]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[1,0,0]]- ready
[[0,1]]- processed
[[0,2]]- layers
1- leftInLayer
0- current
[0,2]- phase
"release"- predecessor
[0,1]
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[1,0,0]]- ready
[[0,1]]- processed
[[0,2]]- layers
2- leftInLayer
1- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[1,0,0]]- ready
[]- processed
[[0,2],[0,1]]- layers
2- leftInLayer
0- current
[0,1]- phase
"remove"
- Discharge one strictly increasing edge from its lower predecessor.
A lower cell becomes ready only after every greater neighbor is removed, so its layer is one plus the maximum successor layer. Direct comparisons avoid int subtraction overflow.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[0,0,0]]- ready
[[0,0]]- processed
[[0,2],[0,1]]- layers
2- leftInLayer
0- current
[0,1]- phase
"release"- predecessor
[0,0]
- Freeze this complete reverse-topological layer.
The layer number is the longest increasing suffix length for cells in this batch. Newly released lower cells must wait for the next batch.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[0,0,0]]- ready
[[0,0]]- processed
[[0,2],[0,1]]- layers
3- leftInLayer
1- current
null- phase
"layer"
- Remove one maximum of the remaining DAG.
Processed coordinates are teaching history. Java needs only the remaining counts, queue, and layer boundaries.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[0,0,0]]- ready
[]- processed
[[0,2],[0,1],[0,0]]- layers
3- leftInLayer
0- current
[0,0]- phase
"remove"
- All cells are peeled; the number of layers is the longest cell count.
A nonempty strict-increase DAG always has a sink. Empty/zero-column matrices have no vertices and return zero.
- matrix
[[-2147483648,0,2147483647]]- remaining
[[0,0,0]]- ready
[]- processed
[[0,2],[0,1],[0,0]]- layers
3- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
3
Empty matrix
Input: [] · Longest strict path in cells: 0
Step 1 of 3: Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
Phase: seed.
Unchanged heights — ✓ removed coordinate
No cells.
Remaining strictly greater successor occurrences — ✓ already removed
No cells.
Coordinate FIFO — front at left
Empty.
Layer number: 0. Pops remaining in the frozen current layer: 0.
Removed coordinates — teaching history
Empty.
Strict increases define the DAG; equal heights have no edge. A lower cell waits for every greater successor, so reverse layers measure the longest suffix, not a shortest route. Zero counts can belong to queued or already removed cells. The current pop may still have pending reverse edges to discharge before the next layer starts.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| matrix | [] |
| remaining | [] |
| ready | [] |
| processed | [] |
| layers | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] matrix) { 5 Objects.requireNonNull(matrix,"matrix");int columns=matrix.length==0?0:matrix[0]==null?-1:matrix[0].length;for(int[] row:matrix)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular matrix");return columns; 6 } 7 public static int longestPath(int[][] matrix) { 8 int columns=validate(matrix);int[][] remaining=new int[matrix.length][columns];ArrayDeque<int[]> ready=new ArrayDeque<>(); 9 for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++) { 10 for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])remaining[r][c]++;} 11 if(remaining[r][c]==0)ready.addLast(new int[]{r,c}); 12 } 13 int layers=0; 14 while(!ready.isEmpty()) { 15 int size=ready.size();layers++; 16 for(int i=0;i<size;i++) { 17 int[] cell=ready.removeFirst(); 18 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]<matrix[cell[0]][cell[1]]&&--remaining[nr][nc]==0)ready.addLast(new int[]{nr,nc});} 19 } 20 } 21 return layers; 22 } 23 public static int baseline(int[][] matrix) { 24 int columns=validate(matrix),best=0;for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++)best=Math.max(best,enumerate(matrix,columns,r,c));return best; 25 } 26 private static int enumerate(int[][] matrix,int columns,int r,int c) { 27 int best=1;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])best=Math.max(best,1+enumerate(matrix,columns,nr,nc));}return best; 28 } 29 } 30
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
- matrix
[]- remaining
[]- ready
[]- processed
[]- layers
0- leftInLayer
0- current
null- phase
"seed"
- All cells are peeled; the number of layers is the longest cell count.
A nonempty strict-increase DAG always has a sink. Empty/zero-column matrices have no vertices and return zero.
- matrix
[]- remaining
[]- ready
[]- processed
[]- layers
0- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
0
Zero-column rows
Input: [[],[]] · Longest strict path in cells: 0
Step 1 of 3: Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
Phase: seed.
Unchanged heights — ✓ removed coordinate
No cells.
Remaining strictly greater successor occurrences — ✓ already removed
No cells.
Coordinate FIFO — front at left
Empty.
Layer number: 0. Pops remaining in the frozen current layer: 0.
Removed coordinates — teaching history
Empty.
Strict increases define the DAG; equal heights have no edge. A lower cell waits for every greater successor, so reverse layers measure the longest suffix, not a shortest route. Zero counts can belong to queued or already removed cells. The current pop may still have pending reverse edges to discharge before the next layer starts.
Cards and removal histories explain control flow; they are not extra Java output or workspace. Exact counts, queues, and static steps remain available below.
| Variable | Value |
|---|---|
| matrix | [[],[]] |
| remaining | [[],[]] |
| ready | [] |
| processed | [] |
| layers | 0 |
| leftInLayer | 0 |
| current | null |
| phase | "seed" |
See the affected Java block
1 import java.util.*; 2 public final class Solution { 3 private static final int[][] DIRECTIONS={{-1,0},{0,1},{1,0},{0,-1}}; 4 private static int validate(int[][] matrix) { 5 Objects.requireNonNull(matrix,"matrix");int columns=matrix.length==0?0:matrix[0]==null?-1:matrix[0].length;for(int[] row:matrix)if(row==null||row.length!=columns)throw new IllegalArgumentException("nonrectangular matrix");return columns; 6 } 7 public static int longestPath(int[][] matrix) { 8 int columns=validate(matrix);int[][] remaining=new int[matrix.length][columns];ArrayDeque<int[]> ready=new ArrayDeque<>(); 9 for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++) { 10 for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])remaining[r][c]++;} 11 if(remaining[r][c]==0)ready.addLast(new int[]{r,c}); 12 } 13 int layers=0; 14 while(!ready.isEmpty()) { 15 int size=ready.size();layers++; 16 for(int i=0;i<size;i++) { 17 int[] cell=ready.removeFirst(); 18 for(int[] d:DIRECTIONS){int nr=cell[0]+d[0],nc=cell[1]+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]<matrix[cell[0]][cell[1]]&&--remaining[nr][nc]==0)ready.addLast(new int[]{nr,nc});} 19 } 20 } 21 return layers; 22 } 23 public static int baseline(int[][] matrix) { 24 int columns=validate(matrix),best=0;for(int r=0;r<matrix.length;r++)for(int c=0;c<columns;c++)best=Math.max(best,enumerate(matrix,columns,r,c));return best; 25 } 26 private static int enumerate(int[][] matrix,int columns,int r,int c) { 27 int best=1;for(int[] d:DIRECTIONS){int nr=r+d[0],nc=c+d[1];if(nr>=0&&nr<matrix.length&&nc>=0&&nc<columns&&matrix[nr][nc]>matrix[r][c])best=Math.max(best,1+enumerate(matrix,columns,nr,nc));}return best; 28 } 29 } 30
Highlight locates the relevant statement or block; one trace step may summarize several assignments.
Read the full static trace
- Count strictly greater successors and seed local maxima.
Strict increase rules out cycles; equal-height neighbors are not edges. Original heights never change, even when source rows alias.
- matrix
[[],[]]- remaining
[[],[]]- ready
[]- processed
[]- layers
0- leftInLayer
0- current
null- phase
"seed"
- All cells are peeled; the number of layers is the longest cell count.
A nonempty strict-increase DAG always has a sink. Empty/zero-column matrices have no vertices and return zero.
- matrix
[[],[]]- remaining
[[],[]]- ready
[]- processed
[]- layers
0- leftInLayer
0- current
null- phase
"complete"
- Return the documented order, optional alphabet, safe list, or path/semester count.
Walkthrough histories are explanatory state; Java output and workspace follow the specific API contract.
- result
0
Test the contract
Input:
Empty or zero-column rows
Output:0No vertices, but row shape still validates.
Input:
Single cell or equal plateau
Output:1Length counts cells and strictness excludes equality.
Input:
Full-int increasing row
Output:correct length without subtractionMIN/MAX comparisons remain safe.
Input:
Shared read-only rows
Output:same value-based answer and preserved row identitiesVertices are coordinates.
Input:
100,000-cell increasing corridor
Output:100,000Main implementation avoids recursive stack limits.
Common mistakes and counterexamples
Treat equal heights as increasing
Counterexample: A 2×2 plateau has answer one, not four.
Use strict comparisons in edge counts and reverse discharge.
Run ordinary shortest-distance BFS
Counterexample: The result is the longest increasing chain among all starts, not the nearest path from one seed.
Prove DAG suffix layers and wait for every greater successor.
Use a globally visited recursive search without memoized lengths
Counterexample: First visiting a shared suffix does not tell another parent its best remaining length.
Memoize numeric suffix answers or use this topological evaluation.
Subtract heights or count edges
Counterexample: MAX−MIN overflows int; one cell has zero edges but answer one.
Compare directly and initialize the first nonempty layer to one.
Follow-ups
Use memoized DFS.
Cache the numeric longest suffix after all child results are known. Main work becomes O(R+B), but Java recursion can still overflow on a long corridor; use explicit frames or retain the iterative implementation.
Return one longest path.
Store successor choices with a consistent tie-break while evaluating the DAG recurrence. Reconstruct from a maximal-length start, verify every strict orthogonal edge, and count O(L) output separately.
Allow nondecreasing moves.
Equal-value edges can form cycles and revisits need a new policy. This DAG proof no longer applies; forbidding coordinate reuse does not restore the same linear algorithm.