Java, O(m+n) space, 19ms beats 95%


  • 0

    Try to extend the 1 sequence in horizontal, vertical, diagonal and anti-diagonal directions.

        public int longestLine(int[][] M) {
            if (M.length == 0 || M[0].length == 0) return 0;
            int m = M.length, n = M[0].length, max = 0;
            int[] colcount = new int[n], diagcount = new int[m+n+1], adiagcount = new int[m+n+1];
            for (int i = 0; i < m; i++) {
                int rowcount = 0;
                for (int j = 0; j < n; j++) {
                    if (M[i][j] == 1) {
                        rowcount++;
                        colcount[j]++;
                        diagcount[i+j]++;
                        adiagcount[i-j+n]++;
                        max = Math.max(max, Math.max(rowcount, Math.max(colcount[j], Math.max(diagcount[i+j], adiagcount[i-j+n]))));
                    } else {
                        rowcount  = colcount[j] = diagcount[i+j] = adiagcount[i-j+n] = 0;
                    }
                }
            }
            return max;
        }
    

Log in to reply
 

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