23ms O(n) solution


  • 0
    X
        public int longestLine(int[][] M) {
            int m = M.length;
            if(m == 0) return 0;
            int n = M[0].length;
            if(n == 0) return 0;
            int[] row = new int[m];
            int[] col = new int[n];
            int[] d1 = new int[m + n - 1];
            int[] d2 = new int[m + n - 1];
            int max = 0;
            
            for(int i = 0;i < m;i++){
                for(int j = 0;j < n;j++){
                    if(M[i][j] == 1){
                        max = Math.max(max, ++row[i]);
                        max = Math.max(max, ++col[j]);
                        max = Math.max(max, ++d1[i + j]);
                        max = Math.max(max, ++d2[n - 1 + i - j]);
                    }
                    else{
                        row[i] = 0;
                        col[j] = 0;
                        d1[i + j] = 0;
                        d2[n - 1 + i - j] = 0;
                    }
                }
            }
            
            return max;
        }
    }
    

    the line need to be consecutive, the for loop of i and j are of the same order of cols, rows, diagonals, so, when we meet a 0, the line at this 4 directions are stopped, set them to 0.


Log in to reply
 

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