329. Longest Increasing Path in a Matrix

Given an integer matrix, find the length of the longest increasing path.

From each cell, you can either move to four directions: left, right, up or down. You may NOT move diagonally or move outside of the boundary (i.e. wrap-around is not allowed).

Example 1:

Input: 
nums = 
[
  [9,9,4],
  [6,6,8],
  [2,1,1]
  ] 

Output: 4 
Explanation: The longest increasing path is [1, 2, 6, 9].

Example 2:

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

Output: 4 
Explanation: The longest increasing path is [3, 4, 5, 6]. Moving diagonally is not allowed.

Thoughts:

1. DFS + memoization:

2. Topological sort: impose an directed edge a -> b if a < b. Then each time, delete the node with out degree zero, then the number of iteration is the result. (from post)

Code: DFS + Memoization: T:O(mn); S:O(mn)

class Solution {
    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0|| matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length, max = 0;
        int dp [][]  = new int [m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                max = Math.max(max, dfs(matrix, m , n, i, j, dp));
            }
        }

        return max;
    }

    private int dfs(int[][] matrix, int m, int n,int i, int j, int [][] dp){
        if(dp[i][j] != 0) return dp[i][j]; // memoization
        int cnt = 1;
        int d[] = {0,1,0,-1,0};
        for(int k = 0; k < 4; k++){
            int x = i + d[k], y= j + d[k + 1];
            if(x < 0 || x >= m || y < 0 || y>= n || matrix[i][j] >= matrix[x][y]) continue;
            cnt = Math.max(cnt, dfs(matrix, m, n, x, y, dp) + 1);
        }

        dp[i][j] = cnt;
        return cnt;
    }
}

Code: Python

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        def dfs(i,j):
            if dp[i][j]: return dp[i][j]
            cur = matrix[i][j]
            dp[i][j] = 1 + max(dfs(i + 1, j) if i + 1 < m  and cur > matrix[i + 1][j] else 0,
                           dfs(i - 1, j) if i and cur > matrix[i - 1][j] else 0,
                           dfs(i, j + 1) if j + 1 < n and cur > matrix[i][j + 1] else 0,
                           dfs(i, j - 1) if j and cur > matrix[i][j - 1] else 0
                          )
            return dp[i][j]

        if not matrix or not matrix[0]: return 0
        m,n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)] 
        return max(dfs(i,j) for j in range (n) for i in range(m))

Code: Topological Sort O(mn * h), where h is the height of the order: (TLE)

class Solution(object):
    def longestIncreasingPath(self, matrix):
        """
        :type matrix: List[List[int]]
        :rtype: int
        """
        if not matrix or not matrix[0]: return 0

        m, n = len(matrix), len(matrix[0])
        count, res = m * n, 0

        while count > 0:
            s = set()
            for i in range(m):
                for j in range(n):
                    if matrix[i][j] == -sys.maxint-1: continue
                    up = (not i) or matrix[i][j] >= matrix[i - 1][j]
                    down = i + 1 == m or matrix[i][j] >= matrix[i + 1][j]
                    left = (not j) or matrix[i][j] >= matrix[i][j - 1]
                    right = j + 1 == n or matrix[i][j] >= matrix[i][j + 1]

                    if up and down and left and right:
                        s.add((i,j))

            for x, y in s:
                matrix[x][y] = -sys.maxint-1
                count -= 1
            res += 1

        return res