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)