AceYourInterviews
Checking sign-in…

108. Longest Increasing Path in a Matrix

AdvancedStrict values form an implicit DAG; reverse topological layers measure longest suffixes

Choose a starting cell and repeatedly move to an orthogonally adjacent cell with a strictly greater value. Return the longest path length over all possible starts.

Equal values cannot extend the path. You are measuring a connected path through cells, not a sorted collection of unrelated matrix values.

Example 1

Input

[[9,9,4],[6,6,8],[2,1,1]]

Output

4

Explanation: One path is 1→2→6→9. Two 9 cells are separate maxima; equal heights do not extend a path.

Example 2

Input

[[MIN,0,MAX]]

Output

3

Explanation: Both direct inequalities are valid without overflowing subtraction.

Example 3

Input

[[7,7],[7,7]]

Output

1

Explanation: No strict edge exists, although all four cells are orthogonally connected.

Example 4

Input

[[],[]]

Output

0

Explanation: Row validation still costs work, but there are no path vertices.

Constraints

  • 0 <= matrix.length <= 105
  • 0 <= total matrix cells <= 105
  • -231 <= matrix[r][c] <= 231 - 1
  • All rows have equal length and are non-null.
Hints
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.

Practice on LeetCode ↗
Code
Saved on this deviceLn 1, Col 1

Reverse layers evaluate shared increasing suffixes

[[9,9,4],[6,6,8],[2,1,1]]
4