Massive Algorithms: LeetCode 329 - Longest Increasing Path in a Matrix

LeetCode 329 - Longest Increasing Path in a Matrix

https://leetcode.com/problems/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:

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

Return 4
The longest increasing path is [1, 2, 6, 9].

Example 2:

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

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

X. Topological Sort
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/129538/BFS-topological-sort
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/129538/BFS-topological-sort
The space is O(mn). The worst case is we have a ascending matrix like this

1, 2, 3, 4
2, 3, 4, 5
3, 4, 5, 6

So there are exactly one edge between each adjecent number. And it's easy to understand that there will be no more than one edge between two numbers.
Time should be O(mn) too, as we are iterating all the edges exactly one time.

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/144558/Java-BFS-Topological-Sort

Inspired by this C++ post, translated into Java version. The idea behind it is BFS Topological Sort: Kahn's Algorithm

    // Topological sorting : BFS   
    // if the problem changes to find longest **non-decreasing** path, topological sorting will not work.
    // e.x   2 2
    //       3 4    
    // 2 and 2 both have outdeg == 1. there is no outdeg == 0 nodes in matrix.
    private static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    private int m, n;
    public int longestIncreasingPath(int[][] matrix) {
        // input validation
        if (matrix == null || matrix.length == 0) 
            return 0;
        // bfs starting from nodes with indegree as 0
        m = matrix.length; n = matrix[0].length;
        int[][] indegree = new int[m][n];
        Queue<int[]> q = new LinkedList();
        for (int row = 0; row < m; row++) {
            for (int col = 0; col < n; col++) {
                for(int i = 0; i < 4; i++) {
                    int nextRow = row + dirs[i][0];
                    int nextCol = col + dirs[i][1];
                    if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && 
                        matrix[row][col] > matrix[nextRow][nextCol]) {
                        indegree[row][col]++;
                    }
                }
                if (indegree[row][col] == 0) q.offer(new int[]{row, col});
            }
        }
        // process graph layer-by-layer
        int len = 0;
        while (!q.isEmpty()) {
            int size = q.size();
            while (size-- > 0) { // consume all nodes in cur layer and add next layer into queue
                int[] coord = q.poll();
                int row = coord[0], col = coord[1];
                for(int i = 0; i < 4; i++) {
                    int nextRow = row + dirs[i][0];
                    int nextCol = col + dirs[i][1];
                    if (nextRow >= 0 && nextRow < m && nextCol >= 0 && nextCol < n && 
                        matrix[row][col] < matrix[nextRow][nextCol]) {
                        if (--indegree[nextRow][nextCol] == 0)     // remove edge
                            q.offer(new int[]{nextRow, nextCol});  // add as next level node
                    }
                }
            }
            len++; // at the end of each layer, increase the length
        }
        return len;
    }

X. DFS + Cache

https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/78308/15ms-Concise-Java-Solution

To get max length of increasing sequences:

Do DFS from every cell
Compare every 4 direction and skip cells that are out of boundary or smaller
Get matrix max from every cell's max
Use matrix[x][y] <= matrix[i][j] so we don't need a visited[m][n] array
The key is to cache the distance because it's highly possible to revisit a cell

Hope it helps!

public static final int[][] dirs = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};

public int longestIncreasingPath(int[][] matrix) {
    if(matrix.length == 0) return 0;
    int m = matrix.length, n = matrix[0].length;
    int[][] cache = new int[m][n];
    int max = 1;
    for(int i = 0; i < m; i++) {
        for(int j = 0; j < n; j++) {
            int len = dfs(matrix, i, j, m, n, cache);
            max = Math.max(max, len);
        }
    }   
    return max;
}

public int dfs(int[][] matrix, int i, int j, int m, int n, int[][] cache) {
    if(cache[i][j] != 0) return cache[i][j];
    int max = 1;
    for(int[] dir: dirs) {
        int x = i + dir[0], y = j + dir[1];
        if(x < 0 || x >= m || y < 0 || y >= n || matrix[x][y] <= matrix[i][j]) continue;
        int len = 1 + dfs(matrix, x, y, m, n, cache);
        max = Math.max(max, len);
    }
    cache[i][j] = max;
    return max;
}

http://algobox.org/longest-increasing-path-in-a-matrix/
https://discuss.leetcode.com/topic/34755/java-dfs-dp-solution

The naive idea is that, start from any cell and do DFS to find the longest increasing path with that cell as the first. This solution is $O(n^2m^2)$ for a matrix of n by m.

Of course, this is too slow and contains a lot of repeated calculations. An optimization is using memoization. Suppose a cell $(i, j)$ has value $v(i, j)$ and the longest increasing path start from $(i, j)$ is $l(i,j)$ . Then we have

1

2

3

4

v[i][j] = 1

for p, q in neighbors(i, j):

    if (v[p][q] < v[i][j]):

         v[i][j] = max(v[i][j], v[p][q] + 1)

Here neighbors(i,j) is just a function to generate all four (if possible) neighbor indices for $(i, j)$

Now we could do a scan through the matrix and apply this formula/subroutine for all cells. During the scan, recursive calls will happen. But that is ok because we can use a memoization matrix to make sure no repeat calculation. The time complexity of the entire algorithm is O(nm) which is linear to the number of cells.

    private static final int[] d = {0, 1, 0, -1, 0};

    public int longestIncreasingPath(int[][] matrix) {

        if (matrix.length == 0) return 0;

        int m = matrix.length, n = matrix[0].length;

        int[][] memo = new int[m][n];

        int ans = 0;

        for (int i = 0; i < m; ++i)

            for (int j = 0; j < n; ++j)

                ans = Math.max(ans, dfs(matrix, m, n, i, j, memo));

        return ans;

}

    private int dfs(int[][] matrix, int m, int n, int i, int j, int[][] memo) {

        if (memo[i][j] == 0) {

            for (int k = 0; k < 4; ++k) {

                int p = i + d[k], q = j + d[k + 1];

                if (0 <= p && p < m && 0 <= q && q < n && matrix[p][q] > matrix[i][j])

                    memo[i][j] = Math.max(memo[i][j], dfs(matrix, m, n, p, q, memo));

}

            memo[i][j]++;

}

        return memo[i][j];

}

DFS+DP - time complexity: O(mn)
https://www.hrwhisper.me/leetcode-longest-increasing-path-matrix/
http://www.fgdsb.com/2015/01/07/longest-increasing-sequence-in-matrix/

直接DFS效率太低，这题主要考DP+记忆化。
DP方程很明显：
opt[i][j] = max{ opt[i+1][j], opt[i-1][j], opt[i][j+1], opt[i][j-1] } +１

这道题给我们一个二维数组，让我们求矩阵中最长的递增路径，规定我们只能上下左右行走，不能走斜线或者是超过了边界。那么这道题的解法要用递归和DP来解，用DP的原因是为了提高效率，避免重复运算。我们需要维护一个二维动态数组dp，其中dp[i][j]表示数组中以(i,j)为起点的最长递增路径的长度，初始将dp数组都赋为0，当我们用递归调用时，遇到某个位置(x, y), 如果dp[x][y]不为0的话，我们直接返回dp[x][y]即可，不需要重复计算。我们需要以数组中每个位置都为起点调用递归来做，比较找出最大值。在以一个位置为起点用DFS搜索时，对其四个相邻位置进行判断，如果相邻位置的值大于上一个位置，则对相邻位置继续调用递归，并更新一个最大值，搜素完成后返回即可，参见代码如下：

    int []dx = { 1 , -1, 0 , 0  };

    int []dy = { 0 , 0 , 1 , -1 };

    public int longestIncreasingPath(int[][] matrix) {

        if (matrix.length == 0) return 0;

        int m = matrix.length, n = matrix[0].length;

        int[][] dis = new int [m][n]; // call it dp or cache

        int ans = 0;

        for (int i = 0; i < m; i++) {

            for (int j = 0; j < n; j++) {

                ans = Math.max(ans, dfs( i, j, m, n, matrix, dis));

}

}

        return ans;

}

    int dfs(int x, int y, int m,int n,int[][] matrix, int[][] dis) {

        if (dis[x][y] != 0) return dis[x][y];

        for (int i = 0; i < 4; i++) {

            int nx = x + dx[i];

            int ny = y + dy[i];

            if (nx >= 0 && ny >= 0 && nx < m && ny < n && matrix[nx][ny] > matrix[x][y]) {

                dis[x][y] = Math.max(dis[x][y], dfs(nx, ny, m, n, matrix, dis));

}

}

        dis[x][y]++;

        return dis[x][y];

}

https://asanchina.wordpress.com/2016/01/20/329-longest-increasing-path-in-a-matrix/

这是一道典型的动态规划，得使用memorandum(备忘录)。我的dfs(r, c)会求以matrix[r][c]为最后一个数字的序列的最大长度。

http://www.zrzahid.com/longest-increasing-path-in-a-matrix/
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/78313/Java-14ms-relative-short-and-easy-to-code-solution-with-explanation.-O(mn)-time-O(mn)-space.-DFS-%2B-DP

1. For each cell, try it's left, right, up and down for smaller number.
2. If it's smaller, means we are on the right track and we should keep going. If larger, stop and return.
3. Treat each cell as a start cell. Calculate and memorize the longest distance for this cell, so we don't need to calculate it again in the future.

Questions and advices are welcome.

    public int longestIncreasingPath(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int[][] cache = new int[matrix.length][matrix[0].length];
        int max = 0;
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                int length = findSmallAround(i, j, matrix, cache, Integer.MAX_VALUE);
                max = Math.max(length, max);
            }
        }
        return max;
    }
    private int findSmallAround(int i, int j, int[][] matrix, int[][] cache, int pre) {
        // if out of bond OR current cell value larger than previous cell value.
        if (i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length || matrix[i][j] >= pre) {
            return 0;
        }
        // if calculated before, no need to do it again
        if (cache[i][j] > 0) {
            return cache[i][j];
        } else {
            int cur = matrix[i][j];
            int tempMax = 0;
            tempMax = Math.max(findSmallAround(i - 1, j, matrix, cache, cur), tempMax);
            tempMax = Math.max(findSmallAround(i + 1, j, matrix, cache, cur), tempMax);
            tempMax = Math.max(findSmallAround(i, j - 1, matrix, cache, cur), tempMax);
            tempMax = Math.max(findSmallAround(i, j + 1, matrix, cache, cur), tempMax);
            cache[i][j] = ++tempMax;
            return tempMax;
        }
    }

TODO X. DP

https://zxi.mytechroad.com/blog/dynamic-programming/leetcode-329-longest-increasing-path-in-a-matrix/

Time complexity: O(mn*log(mn))

  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, 1)); 

    int ans = 0;

    vector<pair<int, pair<int, int>>> cells;

    for (int y = 0; y < m; ++y)

      for (int x = 0; x < n; ++x)

        cells.push_back({matrix[y][x], {x, y}});

    sort(cells.rbegin(), cells.rend());

    vector<int> dirs {0, 1, 0, -1, 0};    

    for (const auto& cell : cells) {

      int x = cell.second.first;

      int y = cell.second.second;

      for (int i = 0; i < 4; ++i) {

        int tx = x + dirs[i];

        int ty = y + dirs[i + 1];

        if (tx < 0 || tx >= n || ty < 0 || ty >= m) continue;

        if (matrix[ty][tx] <= matrix[y][x]) continue;

        dp[y][x] = max(dp[y][x], 1 + dp[ty][tx]);            

}

      ans = max(ans, dp[y][x]);

}

    return ans;

}

http://bookshadow.com/weblog/2016/01/20/leetcode-longest-increasing-path-matrix/

将矩阵matrix按照值从小到大排序，得到列表slist，列表元素(x, y, val)存储原矩阵的(行、列、值)

引入辅助数组dp，dp[x][y]表示从矩阵(x, y)元素出发的最长递增路径长度

遍历slist，同时更新(x, y)左、右、上、下四个相邻元素的dp值

def longestIncreasingPath(self, matrix): """ :type matrix: List[List[int]] :rtype: int """ h = len(matrix) if h == 0: return 0 w = len(matrix[0]) dp = [[1] * w for x in range(h)] slist = sorted([(i, j, val) for i, row in enumerate(matrix) for j, val in enumerate(row)], key=operator.itemgetter(2)) for x, y, val in slist: for dx, dy in zip([1, 0, -1, 0], [0, 1, 0, -1]): nx, ny = x + dx, y + dy if 0 <= nx < h and 0 <= ny < w and matrix[nx][ny] > matrix[x][y]: dp[nx][ny] = max(dp[nx][ny], dp[x][y] + 1) return max([max(x) for x in dp])

参考：https://leetcode.com/discuss/81319/short-python

代码作者使用复数表示矩阵的行、列，十分巧妙。

def longestIncreasingPath(self, matrix): matrix = {i + j*1j: val for i, row in enumerate(matrix) for j, val in enumerate(row)} length = {} for z in sorted(matrix, key=matrix.get): length[z] = 1 + max([length[Z] for Z in z+1, z-1, z+1j, z-1j if Z in matrix and matrix[z] > matrix[Z]] or [0]) return max(length.values() or [0])

X. BFS
http://www.cnblogs.com/grandyang/p/5148030.html
https://leetcode.com/problems/longest-increasing-path-in-a-matrix/discuss/78459/iterative-java-bfs-solution
下面再来看一种BFS的解法，需要用queue来辅助遍历，我们还是需要dp数组来减少重复运算。遍历数组中的每个数字，跟上面的解法一样，把每个遍历到的点都当作BFS遍历的起始点，需要优化的是，如果当前点的dp值大于0了，说明当前点已经计算过了，我们直接跳过。否则就新建一个queue，然后把当前点的坐标加进去，再用一个变量cnt，初始化为1，表示当前点为起点的递增长度，然后进入while循环，然后cnt自增1，这里先自增1没有关系，因为只有当周围有合法的点时候才会用cnt来更新。由于当前结点周围四个相邻点距当前点距离都一样，所以采用类似二叉树层序遍历的方式，先出当前queue的长度，然后遍历跟长度相同的次数，取出queue中的首元素，对周围四个点进行遍历，计算出相邻点的坐标后，要进行合法性检查，横纵坐标不能越界，且相邻点的值要大于当前点的值，并且相邻点点dp值要小于cnt，才有更新的必要。用cnt来更新dp[x][y]，并用cnt来更新结果res，然后把相邻点排入queue中继续循环即可

    public int longestIncreasingPath(int[][] mat) {
        int R = mat.length;
        if(R == 0) return 0;
        int C = mat[0].length;
        if(C == 0) return 0;
        int[][] ref = new int[R][C];
        
        int[][] directions = {{0,1},{0,-1},{1,0},{-1,0}};
        int maxDepth = 1;
        
        for(int i = 0;i<R;i++){
            for(int j = 0;j<C;j++){
                // start bfs from unvisited node
                if(ref[i][j] == 0){
                    Queue<List<Integer>> queue = new LinkedList<List<Integer>>();
                    queue.add(new ArrayList<Integer>(Arrays.asList(i,j)));
                    int depth = 1;
                    while(queue.size() > 0){
                        depth++;
                        int size = queue.size();
                        for(int k = 0;k<size;k++){
                            List<Integer> from = queue.poll();
                            int i1 = from.get(0);
                            int j1 = from.get(1);
                            for(int d=0;d<4;d++){
                                int i2 = i1 + directions[d][0];
                                if(i2 > -1 && i2 < R){
                                    int j2 = j1 + directions[d][1];
                                    if(j2 > -1 && j2 < C){
                                        if(mat[i2][j2] > mat[i1][j1] && depth > ref[i2][j2]){
                                            ref[i2][j2] = depth;
                                            maxDepth = Math.max(maxDepth,depth);
                                            queue.add(new ArrayList<Integer>(Arrays.asList(i2,j2)));
                                        }
                                    }
                                }
                            }
                        }
                    }
                }
            }
        }
        return maxDepth;
    }

X.
http://www.allenlipeng47.com/blog/index.php/2016/01/22/longest-increasing-path-in-a-matrix/

Solution. We can treat each element in matrix as a node. For 2 adjacent nodes, if node1.value < node2.value. Then there is an edge from node1 to node2. In this way, we can transform the matrix to a graph. The problem changes to find the longest path in a directed graph.

In order to find the longest path in graph, each time, we delete the node which out-degree is zero. The number of iteration is the result. Below is a process to calculate the longest path for the graph. The result is 4.

But this top down solution could be O(nm^2) if all nodes forms a line.
DFS is a bottom up solution which guarantee O(nm)

public static class Point{
    int x;
    int y;
    public Point(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

public static int longestIncreasingPath(int[][] matrix) {
    if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0)
        return 0;
    int n = matrix.length, m = matrix[0].length, count = m * n, ans = 0;
    while (count > 0) {
        HashSet<Point> remove = new HashSet<Point>();
        // each round, remove the peak number.
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (matrix[i][j] == Integer.MIN_VALUE)
                    continue;
                boolean up = (i == 0 || matrix[i][j] >= matrix[i - 1][j]);
                boolean bottom = (i == n - 1 || matrix[i][j] >= matrix[i + 1][j]);
                boolean left = (j == 0 || matrix[i][j] >= matrix[i][j - 1]);
                boolean right = (j == m - 1 || matrix[i][j] >= matrix[i][j + 1]);
                if (up && bottom && left && right)
                    remove.add(new Point(i, j));
            }
        }
        for (Point point : remove) {
            matrix[point.x][point.y] = Integer.MIN_VALUE;
            count--;
        }
        ans++;
    }
    return ans;
}

X. http://www.voidcn.com/article/p-gmfwspuq-bqa.html
时间复杂度是O(2^(m+n))

Complexity Analysis

Time complexity :
O(2^{m+n})

The search is repeated for each valid increasing path. In the worst case we can have
O(2^{m+n}) calls. For example:

1 23 . . . n

2 3. . . n+1

3 . . . n+2

. .

m m+1. . . n+m-1

Space complexity :
O(mn). For each DFS we need O(h) space used by the system stack, whereh is the maximum depth of the recursion. In the worst case, O(h) = O(mn)

怎么看出来O(2^{m+n})的呢？这里引用了leetcode解题分析的极端例子，上面那个matrix，递增只有向右或者向下2个方向，左上角的1看做binary tree的root，那么这个tree的depth就是m+n，复杂度就是 2^(m + n) + 2^(m + n - 1) + ... + 2^2 + 2 ^ 1. 可以看成是 m * n * 2^(m + n). m*n忽略，也就是O(2^{m+n})了，指数级，exponential.

    public int longestIncreasingPath(int[][] matrix) {
        if(matrix == null || matrix.length == 0 || matrix[0].length == 0)
            return 0;
        int res = Integer.MIN_VALUE;
        int[][] cache = new int[matrix.length][matrix[0].length];
        for(int i = 0; i < matrix.length; i++){
            for(int j = 0; j < matrix[0].length; j++){
                int max = helper(matrix, i, j, Integer.MIN_VALUE, cache);
                res = Math.max(res, max);
            }
        }
        
        return res;
    }
    
    private int helper(int[][] matrix, int i, int j, int val, int[][]cache){
        if(i < 0 || i >= matrix.length || j < 0 || j >= matrix[0].length)
            return 0;
        if(cache[i][j] != 0){
            return cache[i][j];
        }
        if(matrix[i][j] <= val){
            return 0;
        }
        int up = helper(matrix, i - 1, j, matrix[i][j], cache);
        int down = helper(matrix, i + 1, j, matrix[i][j], cache);
        int left = helper(matrix, i, j - 1, matrix[i][j], cache);
        int right = helper(matrix, i, j + 1, matrix[i][j], cache);
        
        return Math.max(Math.max(up, down), Math.max(left, right)) + 1;
    }

简化：Maximum consucutive path in a matrix
1,2,3
5,8,9
4,7,6
Maximum: 6-7-8-9 return 4
分析复杂度.

LeetCode 329 - Longest Increasing Path in a Matrix

Labels

Popular Posts