Longest Line of Consecutive One in Matrix

Problem Statement

In the task given, we are provided with a binary matrix of size m x n. Our primary objective is to determine the maximum length of a contiguous series of the digit 1 that can be formed in the matrix. This line of ones can traverse in several directions: horizontally along rows, vertically along columns, or diagonally across both left-to-right and right-to-left pathways. Our solution should be the largest count of consecutive ones from any of these directions.

Examples

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.

Approach and Intuition

When addressing the problem of finding the longest line of consecutive ones in a matrix, it's important to efficiently scan through the matrix to track the continuity of ones in all the possible directions:

1. Horizontal Lines:

   • Traverse each row from left to right keeping a count of sequential ones. Reset the count when a zero is encountered.

2. Vertical Lines:

   • Traverse each column top to bottom. Similar to horizontal lines, maintain a count of consecutive ones and reset when zeros are seen.

3. Diagonal Lines:

   • For each direction (top-left to bottom-right, and top-right to bottom-left), commence from each possible starting point on the matrix's perimeter and traverse diagonally, again counting consecutive ones and resetting the count on zeros.

4. Tracking and Updating Maximum Line Length:

   • During the above steps, keep updating a variable that stores the maximum length of consecutive ones found. This ensures that at the end of the traversal through the matrix, this variable contains the answer.

This approach guarantees that each potential line of ones is considered, ensuring the return of the correct maximum length across all directions. Given the constraints, our solution has to manage the scanning of possibly very large matrices efficiently by restricting operations to linear passes and simple arithmetic, emphasizing the need for optimizing each traversal.

Solutions

class Solution {
  public int maxConsecutiveOnes(int[][] matrix) {
    if (matrix.length == 0) return 0;
    int maxCount = 0;
    int[][] cache = new int[matrix[0].length][4];
    for (int i = 0; i < matrix.length; i++) {
      int previousValue = 0;
      for (int j = 0; j < matrix[0].length; j++) {
        if (matrix[i][j] == 1) {
          cache[j][0] = j > 0 ? cache[j - 1][0] + 1 : 1;
          cache[j][1] = i > 0 ? cache[j][1] + 1 : 1;
          int temp = cache[j][2];
          cache[j][2] = (i > 0 && j > 0) ? previousValue + 1 : 1;
          previousValue = temp;
          cache[j][3] = (i > 0 && j < matrix[0].length - 1) ? cache[j + 1][3] + 1 : 1;
          maxCount =
              Math.max(maxCount, Math.max(Math.max(cache[j][0], cache[j][1]), Math.max(cache[j][2], cache[j][3])));
        } else {
          previousValue = cache[j][2];
          cache[j][0] = cache[j][1] = cache[j][2] = cache[j][3] = 0;
        }
      }
    }
    return maxCount;
  }
}