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

Hint: The number of elements in the given matrix will not exceed 10,000.


Solution

Approach #1 Brute Force [Accepted]

Algorithm

The brute force approach is really simple. We directly traverse along every valid line in the given matrix: i.e. Horizontal, Vertical, Diagonal aline above and below the middle diagonal, Anti-diagonal line above and below the middle anti-diagonal. Each time during the traversal, we keep on incrementing the if we encounter continuous 1's. We reset the for any discontinuity encountered. While doing this, we also keep a track of the maximum found so far.

Complexity Analysis

  • Time complexity : . We traverse along the entire matrix 4 times.
  • Space complexity : . Constant space is used.

Approach #2 Using 3D Dynamic Programming [Accepted]

Algorithm

Instead of traversing over the same matrix multiple times, we can keep a track of the 1' along all the lines possible while traversing the matrix once only. In order to do so, we make use of a $ sized array. Here, , , , are used to store the maximum number of continuous 1's found so far along the Horizontal, Vertical, Diagonal and Anti-diagonal lines respectively. e.g. is used to store the number of continuous 1's found so far(till we reach the element ), along the horizontal lines only.

Thus, we traverse the matrix in a row-wise fashion only but, keep updating the entries for every appropriately.

The following image shows the filled values for this matrix:

 0 1 1 0

 0 1 1 0

 0 0 1 1

Longest_Line

While filling up the , we can keep a track of the length of the longest consecutive line of 1's.

Watch this animation for complete process:

!?!../Documents/562_Longest_Line.json:1000,563!?!

Complexity Analysis

  • Time complexity : . We traverse the entire matrix once only.

  • Space complexity : . array of size is used, where and are the number of rows ans coloumns of the matrix.

Approach #3 Using 2D Dynamic Programming [Accepted]

Algorithm

In the previous approach, we can observe that the current entry is dependent only on the entries of the just previous corresponding row. Thus, instead of maintaining a 2-D matrix for each kind of line of 1's possible, we can use a 1-d array for each one of them, and update the corresponding entries in the same row during each row's traversal. Taking this into account, the previous 3-D matrix shrinks to a 2-D matrix now. The rest of the procedure remains same as the previous approach.

Complexity Analysis

  • Time complexity : . The entire matrix is traversed once only.

  • Space complexity : . array of size is used, where is the number of columns of the matrix.

Analysis written by: @vinod23

Submit Solution