Java O(nm) Time DP Solution


  • 35
    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.


  • 1

    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)
    

  • 0
    T

    can anybody explain why we are initializing to 1

    for (int k=0;k<4;k++) dp[i][j][k] = 1;


  • 0

    Space complexity optimization: O(n)

    class Solution {
        public int longestLine(int[][] M) {
            int result = 0;
            if (M.length == 0 || M[0].length == 0) {
                return 0;
            }
            int[][][] record = new int[2][M[0].length + 2][4];
            for (int i = 1; i <= M.length; i++) {
                for (int j = 1; j <= M[0].length; j++) {
                    if (M[i - 1][j - 1] == 1) {
                        record[i%2][j][0] = record[(i - 1) % 2][j][0] + 1;     
                        record[i%2][j][1] = record[i % 2][j - 1][1] + 1;
                        record[i%2][j][2] = record[(i - 1) % 2][j - 1][2] + 1;
                        record[i%2][j][3] = record[(i - 1) % 2][j + 1][3] + 1;
                        for (int k = 0; k < 4; k++) {
                            result = Math.max(result, record[i % 2][j][k]);
                        }
                    } else {
                        for (int k = 0; k < 4; k++) {
                            record[i%2][j][k] = 0;
                        }
                    }
                }
            }
            return result;
        }
    }
    

  • 0
    M

    Great solution! Slightly modified to use direction vector and move dp[i][j][k] = 1 to the same loop that we're try different direction:

    public int longestLine(int[][] M) {
            int m = M.length, max = 0;
            if (m == 0) return max;
            int n = M[0].length;
            int[][][] dp = new int[m][n][4];
            int[][] dir = new int[][]{{-1, 0}, {0, -1}, {-1, -1}, {-1, 1}};
            for (int i = 0; i < m; i++) {
                for (int j = 0; j < n; j++) {
                    if (M[i][j] == 0) continue;
                    for (int k = 0; k < 4; k++) {
                        dp[i][j][k] = 1;
                        int prevI = i + dir[k][0];
                        int prevJ = j + dir[k][1];
                        if (isValid(M, prevI, prevJ)) dp[i][j][k] += dp[prevI][prevJ][k];
                        max = Math.max(max, dp[i][j][k]);
                    }
                }
            }
            return max;
        }
        
        private boolean isValid(int[][] M, int i, int j) {
            return i < M.length && i >= 0 && j < M[0].length && j >= 0;
        }
    

Log in to reply
 

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