Room 04 · The Grind — 2-D Dynamic Programming

Longest Increasing Path In a Matrix

HARD✓ CHIP-TIMEDLC #329 — FULL STATEMENT

The briefingthe full drill, in my own words

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.

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.

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

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

The hintstake 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 boardthe 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 splitstwo 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-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED