329. Longest Increasing Path in a Matrix - cocoder39/coco39_LC GitHub Wiki

329. Longest Increasing Path in a Matrix

Notes 2020:

Option 1: recursion + memo

T = O(m*n)

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        memo = [[0] * n for i in range(m)]
        DIR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        
        def helper(row, col):
            if memo[row][col] > 0:
                return memo[row][col]
            
            res = 1
            for x, y in DIR:
                if 0 <= row+x < m and 0 <= col+y < n and matrix[row][col] > matrix[row+x][col+y]:
                    res = max(res, 1 + helper(row+x, col+y))
            
            memo[row][col] = res
            return res
            
        max_len = 0
        for i in range(m):
            for j in range(n):
                max_len = max(max_len, helper(i, j))
        return max_len

Option 2: min heap

T = O(MN*logMN)

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        min_heap = []
        lengths = [[1] * n for i in range(m)]
        for i in range(m):
            for j in range(n):
                min_heap.append((matrix[i][j], i, j))
        
        heapq.heapify(min_heap)
        
        DIR = [(-1, 0), (1, 0), (0, -1), (0, 1)]
        max_len = 0
        while min_heap:
            num, row, col = heapq.heappop(min_heap)
            max_len = max(max_len, lengths[row][col])
            for x, y in DIR:
                if 0 <= row+x < m and 0 <= col+y < n and matrix[row+x][col+y] > num:
                    lengths[row+x][col+y] = max(lengths[row+x][col+y], lengths[row][col] + 1)
        return max_len

====================================================================================

There are many overlapping subproblem. Therefore this problem can be optimized by DP. dp[i][j] is the longest increasing path starting from matrix[i][j]. dp[i][j] == 0 iff matrixp[i][j] has not been visited yet. dp[i][j] >= 1.

time complexity is O(m * n), each bin would only be visited once.

class Solution {
public:
    int longestIncreasingPath(vector<vector<int>>& matrix) {
        if (matrix.empty())
            return 0;
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0)); //dp[i][j] is the longest increasing path start from cell matrix[i][j]
        
        int res = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dp[i][j] == 0)
                    dfs(matrix, dp, i, j);
                res = max(res, dp[i][j]);
            }
        }
        return res;
    }
private:    
    int dfs(vector<vector<int>>& matrix, vector<vector<int>>& dp, int row, int col) {
        if (dp[row][col] != 0)
            return dp[row][col];
            
        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dirs{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int t = 1;
        
        for (auto dir : dirs) {
            int x = row + dir[0];
            int y = col + dir[1];
            if (x >= 0 && x < m && y >= 0 && y < n && matrix[x][y] > matrix[row][col]) {
                t = max(t, 1 + dfs(matrix, dp, x, y));
            }
        } 
        dp[row][col] = t;
        return t;
    }
};
⚠️ **GitHub.com Fallback** ⚠️