Java easy-to-understand O(m*n) solution


  • 0
    Z

    If using the model of DP to treat this problem, your sub-problem is (for each cell): which line
    ( | , __ , \ , / ) gives the MAX (the direction of arrow totally depends on how you traverse your matrix). Treat each row as if this is the last row of your matrix, and use a 3d array ( int[m][n][4] ) to memoize the result. I saw @compton_scatter has similar idea, but I figured this out myself, and mine is probably little bit cleaner.
    The memoized results of the example is shown below:

    int[][] directions = new int[][]{{-1,-1},{-1,0},{0,-1},{-1,1}};
    
    [0000][1111][1121][0000]
    [0000][1212][2221][0000]
    [0000][0000][0000][3111]
    

    My code:

        public int longestLine(int[][] M) {
            int[][] directions = new int[][]{{-1,-1},{-1,0},{0,-1},{-1,1}};
            if(M.length==0)return 0;
            int[][][] memo = new int[M.length][M[0].length][4];
            int res = 0;
            for(int i=0;i<M.length;i++){
                for(int j=0;j<M[0].length;j++){
                    if(M[i][j]==1){
                        for(int k=0;k<4;k++){
                            int r = i+directions[k][0], c = j+directions[k][1];
                            memo[i][j][k] = 1;
                            if(r>=0&&c>=0&&r<M.length&&c<M[0].length&&M[r][c]==1){
                                memo[i][j][k] += memo[r][c][k];
                                res = Math.max(res, memo[i][j][k]);
                            }
                            res = Math.max(res, memo[i][j][k]);
                        }
                    }
                }
            }
            return res;
        }
    

Log in to reply
 

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