562. Longest Line of Consecutive One In Matrix

/**

* 562. Longest Line of Consecutive One in Matrix

* Given a 01 matrix M, find the longest line of consecutive one in the matrix.

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

* Example:

* Input:

* [[0,1,1,0],

* [0,1,1,0],

* [0,0,0,1]]

* Output: 3

Including the problem here because matrix problems often repeat and have a similar pattern.

See my solution of the problem here:

https://github.com/zcoderz/leetcode/blob/main/src/main/java/google/medium/LongestLine.java

First idea here is to recognize that 1s can appear either as: horizontal, vertical, diagonal or anti-diagonal.

Thus, while iterating the array by rows and columns, you can track per column the maximum number of 1s for each of the 4 ways lines of 1s can be formed.

This can be done via dynamic programming and creating an array such as ‘int [][] dp = new int[cols][4];’. Each column has 4 types of ones to record.

Then as you iterate the rows and columns check what the value was previously for corresponding column.

For horizontal its simply the value in the same column previously – add 1 to it if it was previously 1.

For vertical it’s the value in column one before the current one.

For anti-diagonal, it’s the value in column one greater than the current one.

For diagonal it is the value in row-1, col-1. However, this value gets updated as the loop executes. So, you can store the value reflected in row-1, col-1 in a variable. This would simply be the value you saw in the previous iteration of the column loop.

If current row, column isn’t 1 then reset the corresponding entries in the array as 0.

Here is the code:

public int longestLine(int[][] matrix) {
    int longest = 0;
    int rows = matrix.length;
    if (rows ==0) {
        return 0;
    }
    int cols = matrix[0].length;
    int [][] dp = new int[cols][4];
    //order 0 horizontal, 1, vertical , 2 diagonal , 3 anti diagonal

    for (int row = 0; row < rows; row++) {
        //For diagonal it is the value in row-1, col-1. However, this value gets updated as the loop executes.
        // So, you can store the value reflected in row-1, col-1 in a variable.
        // This would simply be the value you saw in the previous iteration of the column loop.
        int priorDiagonal = 0;
        for (int col = 0; col < cols; col++) {
            if (matrix[row][col] == 1) {
                dp[col][0] = ((col) > 0) ? dp[col-1][0] + 1 : 1;  //horizontal
                dp[col][1] = (row > 0) ? dp[col][1] + 1 : 1; //vertical
                int tmp = dp[col][2];
                dp[col][2] = ((row > 0) && (col > 0)) ? priorDiagonal + 1 : 1;
                priorDiagonal =  tmp ;
                dp[col][3] = ((row > 0) && ((col+1) < cols)) ? dp[col+1][3] + 1 : 1;
                longest = Math.max(dp[col][2], Math.max(dp[col][1], Math.max(dp[col][0], Math.max(longest,
                        dp[col][3]))));
            } else {
                //store the value previously seen for the column[2] (diagonal) for later use.
                priorDiagonal = dp[col][2];
                //If current row, column isn’t 1 then reset the corresponding entries in the array as 0.
                dp[col][0] = dp[col][1] = dp[col][2]  = dp[col][3] = 0;
            }
        }
    }
    return longest;
}