329. Longest Increasing Path in a Matrix

Difficulty: Hard

link: https://leetcode.com/problems/longest-increasing-path-in-a-matrix/

1. DP

$O(mnlogmn)$ runtime,

$O(mn)$ space

DP table紀錄第i,j個cell為起始點的increasing path最長長度，base case是四周鄰居都比自己小的cell，path長度包含自己所以是1，

用sort的方式找到matrix最大值，從最大值開始bottum up建立DP table。

python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        
        nums = sorted([(matrix[i][j], i, j) 
                       for i in range(m) 
                       for j in range(n)], 
                      reverse=True)
        
        ans = 1
        for num, i, j in nums:
            neighbors = [0]
            for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
                if 0 <= x < m and 0 <= y < n and num < matrix[x][y]:
                    neighbors.append(dp[x][y])
            dp[i][j] = max(neighbors) + 1
            ans = max(ans, dp[i][j])
        
        return ans

2. DFS + DP

$O(mn)$ runtime,

$O(mn)$ space

更聰明點，直接用DFS來recursive找到base case。

python

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[None] * n for _ in range(m)]
        
        def dfs(i, j):
            if dp[i][j] is None:
                val = 0
                for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
                    if 0 <= x < m and 0 <= y < n and matrix[i][j] < matrix[x][y]:
                        val = max(val, dfs(x, y))
                dp[i][j] = val + 1
            return dp[i][j]
        
        path_length = 1
        for i in range(m):
            for j in range(n):
                path_length = max(path_length, dfs(i, j))
        
        return path_length

3. BFS (Kahn’s algorithm)

$O(mn)$ runtime,

$O(mn)$ space

應用Kahn’s algorithm，先從indegree為0的cell出發，level-wise的做BFS，找出path的最長長度。

python

class Solution:
    def longestIncreasingPath(self, matrix):
        m, n = len(matrix), len(matrix[0])
        
        # calculate indegree of all cells
        indegree = [[0] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
                    if 0 <= x < m and 0 <= y < n and matrix[i][j] > matrix[x][y]:
                        indegree[i][j] += 1
        
        # start from cells whose indegree is 0
        queue = deque()
        for i in range(m):
            for j in range(n):
                if indegree[i][j] == 0:
                    queue.append((i,j))
        
        # BFS
        path_length = 0
        while queue:
            for _ in range(len(queue)):
                i, j = queue.popleft()
                for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:
                    if 0 <= x < m and 0 <= y < n and matrix[i][j] < matrix[x][y]:
                        indegree[x][y] -= 1
                        if indegree[x][y] == 0:
                            queue.append((x, y))
            path_length += 1
        
        return path_length

tags: leetcode