562. Longest Line of Consecutive One in Matrix

Problem Description

The problem presents a binary matrix (mat), which is simply a grid made up of 0s and 1s. Our goal is to find the maximal length of a continuous line of 1s that could be arranged in any of four possible directions: horizontal, vertical, diagonal from top left to bottom right (referred to as 'diagonal'), and diagonal from top right to bottom left (referred to as 'anti-diagonal'). The task is to return the length of this longest line.

Intuition

To solve this problem, we can execute a comprehensive scan of the matrix. This involves checking each direction for each element in the matrix that is a 1 and updating counts of consecutive 1s in each direction.

The intuition for the solution can be broken down as follows:

1. For each cell that contains a 1 in the matrix, we have the potential to extend a line horizontally, vertically, diagonally, or anti-diagonally.

2. We can maintain four separate 2D arrays (of the same dimensions as the original matrix, with an extra buffer row and column to handle edge cases) to keep track of the maximum line length in each of the four directions at each cell.

   • a[][] for the vertical direction
   • b[][] for the horizontal direction
   • c[][] for the diagonal direction
   • d[][] for the anti-diagonal direction

3. By iterating over each cell in the matrix, we update the arrays for directions only if the current cell is a 1. For example, the length of the vertical line at a[i][j] is 1 plus the length at a[i - 1][j] if the cell at mat[i - 1][j - 1] is a 1.

4. Because we are only interested in consecutive 1s, whenever we hit a 0, the count resets to 0.

5. At every step, we update a variable ans to store the maximum line length found so far, resulting in having the maximum length by the time we end our scan.

6. The use of padding (an extra row and column) in arrays a, b, c, and d allows easy indexing without the need to check the matrix boundaries, which simplifies the logic and makes the code cleaner.

Following this approach allows us to resolve the problem with time complexity that is linear with respect to the number of cells in the matrix (O(m * n)) and with extra space for the four tracking matrices.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution approach for this problem involves dynamic programming to keep track of the longest line of 1s for each of the four directions (horizontal, vertical, diagonal, and anti-diagonal) at every cell. Here is a breakdown of how the implementation works, tying back to the Python code provided:

1. Initialization: The solution first initializes four 2D arrays, a, b, c, and d, each with m + 2 rows and n + 2 columns. These arrays are used to store the maximum length of consecutive ones up to that point in the matrix for each direction. The extra rows and columns serve as a buffer that simplifies boundary condition handling.

2. Iterative Processing: The algorithm iterates through each cell in the matrix using two nested loops. The outer loop goes down each row, and the inner loop goes across each column. Only cells with a value of 1 are processed to extend the lines.

3. Updating Directional Counts: For each cell with a 1, the four arrays are updated as follows:

   • a[i][j] is updated to a[i - 1][j] + 1, incrementing the count of vertical consecutive ones from the top.
   • b[i][j] is updated to b[i][j - 1] + 1, incrementing the count of horizontal consecutive ones from the left.
   • c[i][j] is updated to c[i - 1][j - 1] + 1, incrementing the count of diagonal consecutive ones from the top left.
   • d[i][j] is updated to d[i - 1][j + 1] + 1, incrementing the count of anti-diagonal consecutive ones from the top right.

4. Updating the Answer: The maximum value of the four array cells at the current position (a[i][j], b[i][j], c[i][j], d[i][j]) is compared with the current answer (ans). If any of them is greater, ans is updated. This ensures ans always holds the maximum line length found up to that point.

5. Return the Result: After completely scanning the matrix, the maximum length (ans) is returned as the answer.

The data structures used, in this case, are additional 2D arrays that help us track the solution state as we go, characteristic of dynamic programming. The implementation is relatively straightforward and relies on previous states to compute the current state. This ensures that at any given point in the matrix, we know the longest line of 1s that could be formed in any of the four directions without having to re-scan any part of the matrix, which is efficient and reduces the overall time complexity of the algorithm.

Example Walkthrough

Let's illustrate the solution approach with a small binary matrix example:

1mat = [
2    [0, 1, 1, 0],
3    [0, 1, 1, 1],
4    [1, 0, 0, 1]
5]

Following the steps outlined in the solution approach:

1. Initialization: We create four extra 2D arrays a, b, c, and d, each with dimensions 4 x 5 to accommodate the buffer rows and columns.

2. Iterative Processing: We step through each cell in the matrix one by one.

3. Updating Directional Counts and Answer: We update the counts in our four arrays only at positions where the corresponding cell in mat is 1. Assume ans = 0 at the start.

To better understand, let's look at the updates after processing the first two rows:

After the first row:

1a (vertical)       b (horizontal)    c (diagonal)      d (anti-diagonal)
20 0 0 0 0          0 0 0 0 0         0 0 0 0 0          0 0 0 0 0
30 0 1 2 0          0 0 0 1 2         0 0 0 0 1          0 0 1 2 0
40 0 0 0 0          0 0 0 0 0         0 0 0 0 0          0 0 0 0 0
5ans = 2

Here, ans is 2, as that is the largest count in any of the arrays.

After the second row:

1a (vertical)       b (horizontal)    c (diagonal)      d (anti-diagonal)
20 0 0 0 0          0 0 0 0 0         0 0 0 0 0          0 0 0 0 0
30 0 1 2 0          0 0 0 1 2         0 0 0 0 1          0 0 1 2 0
40 0 2 3 0          0 0 0 1 2 3       0 0 0 1 2          0 0 0 3 1
5ans = 3

After processing the cell mat[1][3], ans updates to 3, as that is now the highest value found.

4. Return the Result: After completely iterating over the matrix, we find that the ans is 3, which indicates the length of the longest continuous line of 1s. We would return 3 in this case.

And so, by iterating over the matrix and updating our directional counts, we can determine that the longest continuous line of 1s in mat spans 3 cells and is found horizontally in the second row.

Solution Implementation

Time and Space Complexity

The time complexity of the provided code is O(m * n), where m is the number of rows and n is the number of columns in the input matrix mat. This complexity arises because the code iterates over each cell of the matrix exactly once, performing a constant number of operations for each cell.

The space complexity of the code is also O(m * n) because it creates four auxiliary matrices (a, b, c, d), each of the same size as the input matrix mat. These matrices are used to keep track of the length of consecutive ones in four directions - horizontal, vertical, diagonal, and anti-diagonal.

Learn more about how to find time and space complexity quickly using problem constraints.