Java solution using DP


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

Log in to reply
 

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