562. Longest Line of Consecutive One in Matrix

Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.

The line could be horizontal, vertical, diagonal, or anti-diagonal.

Example 1:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

Example 2:

Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.

Solution：

class Solution {
    public int longestLine(int[][] mat) {
        int n = mat.length;
        int m = mat[0].length;
        int[][] dp1 = new int[n][m];
        /*
        --->
        */

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (mat[i][j] == 1){
                    if (j == 0){
                        dp1[i][j] = 1;
                    }else{
                        dp1[i][j] = dp1[i][j - 1] + 1;
                    }
                }
            }
        }

        int[][] dp2 = new int[n][m];
        /*
        |
        V
        */

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (mat[i][j] == 1){
                    if (i == 0){
                        dp2[i][j] = 1;
                    }else{
                        dp2[i][j] = dp2[i -1][j] + 1;
                    }
                }
            }
        }

        int[][] dp3 = new int[n][m];
        /*
            \
             V

        */

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                if (mat[i][j] == 1){
                    if (i == 0 || j == 0){
                        dp3[i][j] = 1;
                    }else{
                        dp3[i][j] = dp3[i - 1][j -1] + 1;
                    }
                }
            }
        }

        /*

            /
            V
        */

        int[][] dp4 = new int[n][m];

        for (int i = 0; i < n; i++){
            for (int j = m - 1; j >= 0; j--){
                if (mat[i][j] == 1){
                    if (i == 0|| j == m -1){
                        dp4[i][j] = 1;
                    }else{
                        dp4[i][j] = dp4[i - 1][j + 1] + 1;
                    }
                }
            }
        }

        int result = 0;

        for (int i = 0; i < n; i++){
            for (int j = 0; j < m; j++){
                result = Math.max(result, Math.max(dp1[i][j], Math.max(dp2[i][j], Math.max(dp3[i][j], dp4[i][j]))));
            }
        }



        return result;

    }
}


// TC: O(n^2)
// SC: O(n^2)