Longest Increasing Path in Matrix

Problem Statement

You are given a 2-D grid of integers matrix, where each integer is greater than or equal to 0.

Return the length of the longest strictly increasing path within matrix.

From each cell within the path, you can move either horizontally or vertically. You may not move diagonally.

Example 1:

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

Output: 4

Explanation: The longest increasing path is [1, 2, 3, 6] or [1, 2, 3, 5].

Example 2:

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

Output: 7

Explanation: The longest increasing path is [1, 2, 3, 4, 5, 6, 7].

Constraints:

• 1 <= matrix.length, matrix[i].length <= 100

Recommended Time and Space Complexity

You should aim for a solution with O(m*n) time and O(m*n) space, where m is the number of rows and n is the number of columns in the matrix.

Hint 1

Consider using Depth-First Search (DFS) to explore possible paths.

Hint 2

Implement memoization (dynamic programming) to avoid redundant calculations. Store the length of the longest increasing path starting from each cell.

Hint 3

Think about topological sort as an alternative approach. Identify the in-degree of each cell and process them in a specific order.

Solution

Recursion

def longest_increasing_path(matrix: list[list[int]]) -> int:
    rows, cols = len(matrix), len(matrix[0])
    directions = [[-1, 0], [1, 0], [0, -1], [0, 1]]

    def dfs(r, c, prev_val):
        if (min(r, c) < 0 or r >= rows or
            c >= cols or matrix[r][c] <= prev_val
        ):
            return 0

        res = 1
        for d in directions:
            res = max(res, 1 + dfs(r + d[0], c + d[1], matrix[r][c]))
        return res

    lip = 0
    for r in range(rows):
        for c in range(cols):
            lip = max(lip, dfs(r, c, float('-inf')))
    return lip

Time complexity: O(m * n * 4 ^ {m * n}) Space complexity: O(m * n)