Longest Increasing Path in a Matrix

Problem in Plain English

Given an integer grid, find the length of the longest path that moves up, down, left, or right to strictly larger values. Every cell alone counts as a path of length 1.

Problem Statement

Given an $m \times n$ integer grid matrix, return the length of the longest strictly increasing path in it.

From each cell you may move to any of the four orthogonal neighbours (never diagonally and never outside the grid) whose value is strictly greater than the current cell. For matrix = [[9,9,4],[6,6,8],[2,1,1]] the answer is 4 via the trail [1, 2, 6, 9].

Constraints

m equals matrix.length, the number of rows.
n equals the length of each row; the grid is rectangular.
$1 \le m,n \le 200$
Each cell value is an integer between $0$ and $2^{31}-1$ , inclusive.

Examples

Example 1

Input: matrix = [[9,9,4],[6,6,8],[2,1,1]]
Output: 4

Coordinates (2,1) → (2,0) → (1,0) → (0,0) give values 1 → 2 → 6 → 9, so four cells form a legal path. Equal adjacent 9s and 1s cannot extend it. Every starting cell has length at most 4, as the dry runs show.

Example 2

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

One longest path is (0,0) → (0,1) → (0,2) → (1,2), with values 3 → 4 → 5 → 6 and length 4. Another starts at the centre 2. The bottom-left 2 cannot jump diagonally to the centre or cross an equal 2; checking only the global minimum would miss valid best starting points.

Example 3

Input: matrix = [[1]]
Output: 1

There are no neighbours, but the starting cell itself counts. The answer is 1 rather than 0.

Example 4

Input: matrix = [[7,7],[7,7]]
Output: 1

Every orthogonal neighbour is equal, so no move is strictly increasing. Four available cells do not make a path of length four; each start stops immediately.

Intuition

Treat each cell as a state whose answer is the longest increasing path starting there. Each legal move goes to a larger value, so a path cannot return to a cell and the dependency graph has no cycles. A cell alone contributes one; otherwise its answer is one plus the largest answer among its greater neighbours. In Example 1, the same suffix 6 → 9 is needed by both 2 and 1. Remembering a completed suffix avoids exploring it repeatedly. Count cells, rather than moves: 1 → 2 → 6 → 9 has length 4.

Approaches

Raw Depth-First Search

Solution Details

Reveal Raw Depth-First Search: intuition, complexity, and code

Intuition

Explore every increasing continuation from every starting cell, without storing completed answers. A frame holds the current coordinates, the next direction to try, and the best length found so far. An explicit stack performs the same depth-first search as recursive calls while allowing a legal path longer than a language call stack. Shared suffixes such as 6 → 9 in Example 1 are still recomputed.

Step-by-Step Logic

Scan every starting coordinate in row-major order and push a frame [row, column, next direction, best], initially with direction 0 and best 1. Example 1 begins at (0,0), value 9, and finishes with length 1.
Check neighbours in down, up, right, left order. Reject out-of-bounds or non-increasing moves before pushing a child frame; advancing the parent direction first records where to resume.
When a child finishes all four directions, pop it and replace the parent best by the larger of its old value and one plus the child length. For start (0,2), the branch 4 → 8 and the branch 4 → 9 each return 2.
Finish each root and update the global answer. Repeated suffixes are searched again: starting at (2,0) recomputes 2 → 6 → 9 and returns 3.
At (2,1), try 1 → 6 → 9 for length 3, then 1 → 2 → 6 → 9 for length 4. The last start (2,2) returns 2, leaving the final maximum 4.

Why It Works

For a cell with no greater neighbour, its only path contains that cell and has length 1. Otherwise every legal path chooses exactly one greater neighbour first, so its maximum length is one plus the maximum suffix length returned by those neighbours. Strict increases rule out revisiting a cell, so search terminates. Each frame checks all four directions and combines every legal child before returning its best value to the parent. Induction from terminal cells proves each returned length correct. The outer loops include every possible start, so their maximum is the global answer.

Dry Run

Raw Depth-First Search: variable states at each step
Root / event	Frame or child transition (down, up, right, left)	Completed root length	Global best
(0,0), 9	all directions rejected; pop best 1	1	0 → 1
(0,1), 9	equal 9 and lower neighbours rejected; pop 1	1	1
(0,2), 4	push (1,2), 8; leaf 1 raises root best 1 → 2; push (0,1), 9; leaf 1 keeps best 2	2	1 → 2
(1,0), 6	push (0,0), 9; leaf 1 raises best 1 → 2; equal 6 rejected	2	2
(1,1), 6	push (0,1), 9; return 1 gives best 2; push (1,2), 8; return 1 keeps best 2	2	2
(1,2), 8	no greater neighbour; pop 1	1	2
(2,0), 2	push (1,0), 6, then (0,0), 9; pop 9 with 1; pop 6 with 2; root best 1 → 3	3	2 → 3
(2,1), 1; up branch	push (1,1), 6; its 9 and 8 children each return 1; pop 6 with 2; root best 1 → 3	pending	3
(2,1), 1; left branch	equal right 1 rejected; push (2,0), 2 → (1,0), 6 → (0,0), 9; returns 1, 2, 3; root best 3 → 4	4	3 → 4
(2,2), 1	push (1,2), 8; return 1 raises best 1 → 2; equal left 1 rejected	2	4; return 4

Complexity Analysis

Time Complexity

O(mn \cdot 4^{mn})

Space Complexity

O(mn)

Let V = mn. Each of V roots may explore a search tree of depth at most V with up to four children per frame. Summing levels gives O(4^V) work per root, so O(V × 4^V) is a deliberately loose upper bound, not a tight claim. Every frame stores four scalars and scans four neighbours. At most V frames coexist because values strictly increase; Java preallocates V frame slots, while Python and JavaScript grow their heap stacks as needed. Total frame allocations over the run may be exponential, but peak auxiliary storage is O(V), and there is no copied path or visited grid. This baseline is for understanding and small branching inputs, not arbitrary 200 by 200 grids; a flat grid finishes in O(V).

Code

Solution.java

1class Solution {2    private static final int[][] DIRS = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};3
4    public int longestIncreasingPath(int[][] matrix) {5        int m = matrix.length, n = matrix[0].length;6        // Each heap frame holds row, column, next direction, and best suffix length.7        int[][] stack = new int[m * n][4];8        int answer = 0;9        for (int r = 0; r < m; r++) {10            for (int c = 0; c < n; c++) {11                int top = 0;12                stack[0][0] = r; stack[0][1] = c;13                stack[0][2] = 0; stack[0][3] = 1;14                while (top >= 0) {15                    int[] frame = stack[top];16                    if (frame[2] == 4) {17                        int length = frame[3];18                        top--;19                        if (top >= 0) stack[top][3] = Math.max(stack[top][3], 1 + length);20                        else answer = Math.max(answer, length);21                        continue;22                    }23                    // Advance before pushing a child: the parent resumes at its next direction.24                    int d = frame[2]++;25                    int nr = frame[0] + DIRS[d][0], nc = frame[1] + DIRS[d][1];26                    if (nr < 0 || nr >= m || nc < 0 || nc >= n27                            || matrix[nr][nc] <= matrix[frame[0]][frame[1]]) continue;28                    // Strict increase prevents cycles, so at most m*n frames can be active.29                    top++;30                    stack[top][0] = nr; stack[top][1] = nc;31                    stack[top][2] = 0; stack[top][3] = 1;32                }33            }34        }35        return answer;36    }37}

Hints

Hint 1

For a fixed starting cell, what happens after choosing its first greater neighbour?

Hint 2

Strict increases prevent cycles. The best suffix from a cell does not depend on which earlier route reached it.

Hint 3

Store 1 plus the maximum completed greater-neighbour length. Use explicit continuation frames if a path may exceed native recursion limits.

Edge Cases

A single cell and an all-equal grid both return 1; equal values never connect.
Single-row or single-column inputs allow two directions only. Increasing [0,1,2] has length 3; [2,1,0] also has length 3 by moving backwards.
A 200 by 200 snake can use all 40,000 cells. An explicit heap stack handles its depth without adjusting runtime recursion limits.
Values 0 and 2147483647 are legal; compare directly rather than subtracting or adding a sentinel to a value.
Multiple routes may merge into the same suffix, and disconnected local minima may have different lengths; evaluate every start.

Common Mistakes and Interview Tips

Using >= instead of > allows equal-valued cycles and invalid paths.
Caching on entry records an unfinished answer. Write memo only after all four directions have contributed.
Marking a cell globally visited and skipping it later loses its suffix length; reuse a completed numerical memo value instead.
Advancing a frame direction after returning from a child can repeatedly explore that child. Advance before the push and propagate its completed length on pop.
Recursive DFS may overflow Python, JavaScript or Java call stacks on a legal 40,000-cell path even when memoization makes the work linear.
Returning moves rather than visited cells makes a leaf length 0 instead of 1. Sorting values without retaining neighbour coordinates also admits illegal jumps.
Do not claim the unmemoized baseline handles every maximum-size input: its repeated suffix exploration is exponential. Explain the shared-state recurrence before the memoization optimization.

Key Takeaway

When strict progress makes dependencies acyclic, define one answer per state and cache only after its dependencies finish. Memoized DFS then visits each state and its outgoing edges once; explicit continuation frames preserve that recurrence on deep inputs.