An O(nm) DP solution with explanations


  • 2
    L

    A critical observation that the length of the longest increasing path must be finite, i.e., the path cannot be a cycle. This observation encourages us to design a concise DP solution.

    Let dp[i][j] indicate the maximum length of all possible increasing path starting from position (i, j). Then we have the following recurrence.

    1. dp[i][j] = 1, if matrix[i][j]is greater than any of its
      neighbors.
    2. dp[i][j] = 1 + max(dp[x][y]), where (x, y) is any direct neighbor
      of (i, j) satisfying matrix[i][j] < matrix[x][y]. This simply means that
      we try to move one step forward, and among at most four possible
      longest subpaths, we choose the longest one.

    The final answer is max(dp[i][j]). This DP approach clearly requires both O(nm) time and space, where n and m are the two dimensions of the given matrix.

    // Java Code
    public class Solution {
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        int[][] f;
        
        int dp(int[][] a, int i, int j) {
            if (f[i][j] > 0) return f[i][j]; // f[i][j] has been computed already.
            f[i][j] = 1; // also works for base cases.
            for (int k=0; k<4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < a.length && y >= 0 && y < a[0].length && a[i][j] < a[x][y])
                    f[i][j] = Math.max(f[i][j], 1 + dp(a, x, y));
            }
            return f[i][j];
        }
        
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0) return 0;
            f = new int[matrix.length][matrix[0].length];
            int ans = 0;
            for (int i=0; i<matrix.length; i++)
                for (int j=0; j<matrix[0].length; j++)
                    ans = Math.max(ans, dp(matrix, i, j));
            return ans;
        }
    }
    

    Remark. The code above is a top-down implementation. One can also implement it in a bottom-up manner. However, unlike many common DP problems, it requires a topological sort to determine the correct order to compute, i.e., when we try to compute dp[i][j], all the dp[x][y]'s must be computed already. The topological sort can be done by a simple BFS or DFS (though we can already solve this problem by a DFS/BFS). Alternatively, one can achieve a correct topological order by simply sorting all the indices (i, j) in non-increasing order where (i1, j1) < (i2, j2) if and only if matrix[i1][j1] < matrix[i2][j2]. This idea is in some sense cute but costs an additional log(nm) factor due to sorting.


  • -1
    H

    How could it be O(mn)
    There is O(mn) loop in longestIncreasingPath. That loop call dp, which is O(mn) instead of O(1).
    So your time complexity is O(mn*mn)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.