Longest Increasing Path In a Matrix

HARD✓ CHIP-TIMEDLC #329 — FULL STATEMENT ↗

The drill: In a grid of numbers, find the length of the longest path that strictly increases at every step, moving only up, down, left, or right between adjacent cells.

THE BRIEFING — THE FULL DRILL, IN MY OWN WORDS

A grid of numbers arrives, and the task is to find the length of the longest path through it where every step strictly increases in value from the cell before it.

Moves are limited to the four adjacent directions — up, down, left, or right — never diagonal, and a path can start from any cell in the grid, not just a corner. Because every step must strictly increase, no cell can ever be revisited within the same path.

The output is the length of the single longest such increasing path found anywhere in the grid, counted in number of cells visited.

EX 01

matrix = [[5, 7, 3], [2, 8, 9], [1, 4, 6]]

→ 6

THE BOARD'S EXAMPLE

EX 02

matrix = [[1]]

→ 1

MINIMUM SIZE, SINGLE CELL

EX 03

matrix = [[1, 1], [1, 1]]

→ 1

ALL EQUAL — NO STRICT INCREASE POSSIBLE

grid values can repeat, be negative, zero, or positive
movement is limited to the four orthogonal directions, no diagonals
a path never revisits a cell since values must strictly increase
grids stay small enough for an O(r·c) cached search

THE HINTS — TAKE ONLY WHAT YOU NEED

HINT 1 THE NUDGE

Strictly increasing values along the path already forbid revisiting any cell — so despite the grid's four-directional edges, there's no cycle to worry about.

HINT 2 THE STRUCTURE

Treat each cell as the start of its own search: the longest run beginning there is 1 plus the best run beginning at any strictly-larger neighbor. That's a recursive definition, and it doesn't care which cell asked first.

HINT 3 ONE STEP FROM THE ANSWER

Cache the answer for a cell the first time it's computed. Every other path that later reaches that same cell reads the cached length instead of re-walking everything downhill from it.

COACH'S BOARD — THE PATTERN, STEP BY STEP

THE CACHED CLIMBPATTERN · DFS + MEMO PER CELLmatrix = [[5,7,3],[2,8,9],[1,4,6]]

STEP 1

Start the search at (2,0), value 1 — every cell seeds its own increasing run. DFS dives toward strictly larger neighbors first.

STEP 1 / 12 · ← → WORK TOO

THE SPLITS — TWO PACES, TWO LANGUAGES

grind/longest-increasing-path-in-a-matrix.py — RACE PACE

LANG ▸

PACE ▸

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        memo = [[0] * cols for _ in range(rows)]

        def dfs(r, c):
            if memo[r][c]:
                return memo[r][c]
            best = 1
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            memo[r][c] = best
            return best

        return max(dfs(r, c) for r in range(rows) for c in range(cols))

TIME O(R·C)SPACE O(R·C)PYTHON · RACE PACE · 18 LN

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]

        def dfs(r, c):
            best = 1
            for dr, dc in dirs:
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and matrix[nr][nc] > matrix[r][c]:
                    best = max(best, 1 + dfs(nr, nc))
            return best

        return max(dfs(r, c) for r in range(rows) for c in range(cols))

TIME O(4^(R·C))SPACE O(R·C)PYTHON · TRAINING PACE · 14 LN

class Solution {
    private static final int[][] DIRS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    private int rows, cols;
    private int[][] matrix;
    private int[][] memo;

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        rows = matrix.length;
        cols = matrix[0].length;
        memo = new int[rows][cols];
        int best = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                best = Math.max(best, dfs(r, c));
            }
        }
        return best;
    }

    private int dfs(int r, int c) {
        if (memo[r][c] != 0) return memo[r][c];
        int best = 1;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                best = Math.max(best, 1 + dfs(nr, nc));
            }
        }
        memo[r][c] = best;
        return best;
    }
}

TIME O(R·C)SPACE O(R·C)JAVA · RACE PACE · 33 LN

class Solution {
    private static final int[][] DIRS = { { -1, 0 }, { 1, 0 }, { 0, -1 }, { 0, 1 } };
    private int rows, cols;
    private int[][] matrix;

    public int longestIncreasingPath(int[][] matrix) {
        this.matrix = matrix;
        rows = matrix.length;
        cols = matrix[0].length;
        int best = 0;
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                best = Math.max(best, dfs(r, c));
            }
        }
        return best;
    }

    private int dfs(int r, int c) {
        int best = 1;
        for (int[] d : DIRS) {
            int nr = r + d[0], nc = c + d[1];
            if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && matrix[nr][nc] > matrix[r][c]) {
                best = Math.max(best, 1 + dfs(nr, nc));
            }
        }
        return best;
    }
}

TIME O(4^(R·C))SPACE O(R·C)JAVA · TRAINING PACE · 29 LN

✓ CHIP-TIMED — ALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED