Java O(nm) Time DP Solution


  • 28
    public int longestLine(int[][] M) {
        int n = M.length, max = 0;
        if (n == 0) return max;
        int m = M[0].length;
        int[][][] dp = new int[n][m][4];
        for (int i=0;i<n;i++) 
            for (int j=0;j<m;j++) {
                if (M[i][j] == 0) continue;
                for (int k=0;k<4;k++) dp[i][j][k] = 1;
                if (j > 0) dp[i][j][0] += dp[i][j-1][0]; // horizontal line
                if (j > 0 && i > 0) dp[i][j][1] += dp[i-1][j-1][1]; // anti-diagonal line
                if (i > 0) dp[i][j][2] += dp[i-1][j][2]; // vertical line
                if (j < m-1 && i > 0) dp[i][j][3] += dp[i-1][j+1][3]; // diagonal line
                max = Math.max(max, Math.max(dp[i][j][0], dp[i][j][1]));
                max = Math.max(max, Math.max(dp[i][j][2], dp[i][j][3]));
            }
        return max;
    }
    

    Note that each cell of the DP table only depends on the current row or previous row so you can easily optimize the above algorithm to use only O(m) space.


  • 0

    Clean code and easy to understand. Thanks!


  • 1
    G

    Did you interchange diagonal and anti-diagonal comments?
    And shouldn't you be doing max = max of (dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3], max)?


  • 0
    K

    @gova2009 thats what @compton_scatter is doing in the last two lines of the second for loop to get the max


  • 0
    G

    My bad, I didn't observe the nested Math.max.
    But the comment should be reversed, isn't it?


  • 0
    K

    @gova2009 the comments are valid. diagonal is left to right and downwards and anti-diagonal is left to right and upwards


  • 0
    K

    @compton_scatter clear and simple, like it.


  • 0
    K

    @gova2009 it will have the same result, I believe.


  • 0

    I also solved it using similar Idea.

        int [] rdir = new int [] { 0, 1, 1,  1 };
        int [] cdir = new int [] { 1, 1, 0, -1 };
        
        public int longestLine(int[][] M) {
            if (M.length == 0) return 0;
            int max = 0;
            
            int [][][] dp = new int [M.length][M [0].length][4];
                    
            for (int row = 0; row < M.length; row ++)
                for (int col = 0; col < M [0].length; col ++)
                    if (M [row][col] == 1)
                        for (int idx = 0; idx < 4; idx ++) max = Math.max (max, dfs (M, dp, row, col, idx));
            
            return max;
        }
        
        private int dfs (int [][] M, int [][][] dp, int row, int col, int idx) {
            if (row < 0 || row >= M.length || col < 0 || col >= M [0].length || M [row][col] != 1) return 0;
            if (dp [row][col][idx] != 0) return dp [row][col][idx];
            int count = 1;
            count += dfs (M, dp, row + rdir [idx], col + cdir [idx], idx);
            return dp [row][col][idx] = count;
        }
    

  • 0
    G

    @kmv

    I do think it interchanges diagonal and anti-diagonal comments.

    if (j > 0 && i > 0) dp[i][j][1] += dp[i-1][j-1][1]; // anti-diagonal line (wrong. should diagonal line)
    if (i > 0) dp[i][j][2] += dp[i-1][j][2]; // vertical line
    if (j < m-1 && i > 0) dp[i][j][3] += dp[i-1][j+1][3]; // diagonal line (wrong. should anti-diagonal line)
    

Log in to reply
 

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