Leetcode 562. Longest Line of Consecutive One in Matrix

Problem

In this problem, we are given a binary matrix i.e., a matrix with only 0s and 1s. The goal is to find the longest line of consecutive 1s in the matrix. This line could be horizontal, vertical, diagonal or anti-diagonal.

For example:

Consider the binary matrix: [[0,1,1,0], [0,1,1,0], [0,0,0,1]]

In the above matrix, the longest line of consecutive 1s is of length 3, which is the diagonal line [1, 1, 1] starting from matrix[1][1], matrix[2][2] and matrix[3][3].

Approach

We can solve this problem by using dynamic programming approach. We store the number of 1s in four different directions i.e., horizontal, vertical, diagonal, and anti-diagonal from each point. If the element in the current position is 1 then we increment the count by 1 with respect to previous count otherwise we keep it as zero.

Once we update the count at each position, we also track the maximum count obtained so far. At the end, this maximum count will be our solution.

Example

Let’s walk through the problem with the following example:

Consider the binary matrix: [[0,1,1,0], [0,1,1,0], [0,0,0,1]]

After first iteration, our dp array will look like as follows: [[[0, 0, 0, 0], [1, 1, 1, 0], [2, 2, 1, 0], [0, 0, 0, 1]], [[0, 0, 0, 0], [1, 2, 1, 0], [2, 1, 2, 0], [0, 0, 0, 1]], [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [1, 1, 1, 3]]]

At each 1 in the matrix, we have 4 values which denotes the count of consecutive 1s in horizontal, vertical, diagonal, and anti-diagonal respectively from that point. The maximum out of these 4 values is the maximum length of consecutive 1s that we can get from that point.

After iterating over the whole matrix, our max_length will result in 3 which is the maximum value in our dp array.

Solution

1
2python
3class Solution:
4    def longestLine(self, mat):
5        m = len(mat)
6        n = len(mat[0])
7        max_length = 0
8        dp = [[0, 0, 0, 0] for _ in range(m*n)]
9
10        for i in range(m):
11            for j in range(n):
12                if mat[i][j] == 1:
13                    if j > 0: dp[i][j][0] = dp[i][j - 1][0] + 1
14                    else: dp[i][j][0] = 1
15                    if i > 0: dp[i][j][1] = dp[i - 1][j][1] + 1
16                    else: dp[i][j][1] = 1
17                    if i > 0 and j > 0: dp[i][j][2] = dp[i - 1][j - 1][2] + 1
18                    else: dp[i][j][2] = 1
19                    if i > 0 and j < n - 1: dp[i][j][3] = dp[i - 1][j + 1][3] + 1
20                    else: dp[i][j][3] = 1
21                    max_length = max(max_length, max(dp[i][j]))
22
23        return max_length

Note

Ensure the matrix is not empty before applying the DP method to avoid issues (like IndexErrors).## Solution in JavaScript

Here's a JavaScript solution. This solution follows the same principles outlined in the approach above, but implements the sequence checking logic in the form of a helper function, called checkOne.

1
2javascript
3function longestLine(M) {
4  if(M.length === 0) return 0;
5  var max = 0;
6  
7  function checkOne(i, j, dx, dy) {
8    var n = 0;
9
10    for(var x = 0; x < 4; x++, i += dx, j += dy)  {
11      if(i < 0 || i >= M.length || j < 0 || j >= M[0].length || M[i][j] === 0) return;
12      n++;
13    }
14    max = Math.max(max, n);
15  }
16
17  for(var i = 0; i < M.length; i++)  {
18    for(var j = 0; j < M[0].length; j++)  {
19      if(M[i][j] === 1) {
20        checkOne(i, j, -1, 0);
21        checkOne(i, j, 0, -1);
22        checkOne(i, j, -1, -1);
23        checkOne(i, j, -1, 1);
24      }
25    }
26  }
27  return max;
28}

Solution in Java

In Java, we can do this problem in a similar way. As Java is a statically-typed language, we initialize our dynamic programming array with specific dimensions, and use a separate variable to store our maximum length.

1
2java
3class Solution {
4    public int longestLine(int[][] M) {
5        if (M.length == 0) return 0;
6        int m = M.length, n = M[0].length, max = 0;
7        int[][][] dp = new int[m][n][4];
8        
9        for (int i = 0; i < m; i++) {
10            for (int j = 0; j < n; j++) {
11                if (M[i][j] == 1) {
12                    dp[i][j][0] = j > 0 ? dp[i][j - 1][0] + 1 : 1;
13                    dp[i][j][1] = i > 0 ? dp[i - 1][j][1] + 1 : 1;
14                    dp[i][j][2] = i > 0 && j > 0 ? dp[i - 1][j - 1][2] + 1 : 1;
15                    dp[i][j][3] = i > 0 && j < n - 1 ? dp[i - 1][j + 1][3] + 1 : 1;
16                    
17                    max = Math.max(max, Math.max(Math.max(dp[i][j][0], dp[i][j][1]), Math.max(dp[i][j][2], dp[i][j][3])));
18                }
19            }
20        }
21
22        return max;
23    }
24}

All three solutions have a time complexity of O(m * n), where m and n are the dimensions of the binary matrix. They also have a space complexity of O(m * n), since we're using a dp matrix or array to store intermediate results. These solutions implement the dynamic programming approach thoroughly and efficiently.