#329

Longest Increasing Path in a Matrix

hard· 2-D DPruns: 0

Given an m x n integer matrix, return the length of the longest strictly increasing path. From each cell you can move in four directions (up, down, left, right). You may not move diagonally or outside the matrix boundary.

wpm 0acc 100%time 0:000 / 899

class Solution:
    def longestIncreasingPath(
        self, matrix: list[list[int]]
    ) -> int:
        rows, cols = len(matrix), len(matrix[0])
        memo = {}

        def dfs(r: int, c: int, prev: int) -> int:
            if (
                r < 0
                or r >= rows
                or c < 0
                or c >= cols
                or matrix[r][c] <= prev
            ):
                return 0
            if (r, c) in memo:
                return memo[(r, c)]
            curr = matrix[r][c]
            best = 1 + max(
                dfs(r + 1, c, curr),
                dfs(r - 1, c, curr),
                dfs(r, c + 1, curr),
                dfs(r, c - 1, curr),
            )
            memo[(r, c)] = best
            return best

        return max(
            dfs(r, c, float("-inf"))
            for r in range(rows)
            for c in range(cols)
        )

click the box to focus · tab inserts 4 spaces · backspace to correct · esc to pause

desktop only

codedrill is a typing game and needs a real keyboard. open this on a laptop or desktop to practice.

you can still browse problems and sections from your phone.