Problem Description

You are given an m x n binary matrix mat containing only 0s and 1s. Your task is to find the length of the longest line of consecutive 1s in the matrix.

A line of consecutive 1s can be formed in four possible directions:

• Horizontal: A sequence of 1s in the same row (left to right)
• Vertical: A sequence of 1s in the same column (top to bottom)
• Diagonal: A sequence of 1s going from top-left to bottom-right
• Anti-diagonal: A sequence of 1s going from top-right to bottom-left

The solution uses dynamic programming with four 2D arrays (a, b, c, d) to track the length of consecutive 1s ending at each position in all four directions:

• a[i][j]: Length of consecutive 1s ending at position (i,j) in the vertical direction
• b[i][j]: Length of consecutive 1s ending at position (i,j) in the horizontal direction
• c[i][j]: Length of consecutive 1s ending at position (i,j) in the diagonal direction
• d[i][j]: Length of consecutive 1s ending at position (i,j) in the anti-diagonal direction

The arrays are padded with extra rows and columns (size (m+2) x (n+2)) to handle boundary cases. For each cell containing a 1 in the original matrix, the algorithm updates the consecutive count by adding 1 to the count from the previous cell in each respective direction:

• Vertical: a[i][j] = a[i-1][j] + 1
• Horizontal: b[i][j] = b[i][j-1] + 1
• Diagonal: c[i][j] = c[i-1][j-1] + 1
• Anti-diagonal: d[i][j] = d[i-1][j+1] + 1

The maximum value among all these counts across all positions gives the answer.

Intuition

The key insight is that finding the longest line of consecutive 1s is essentially a counting problem where we need to track how many 1s we've seen in a row along different directions.

Think about how you would manually count consecutive 1s in a line - you'd start from a position and keep counting as long as you encounter 1s. When you hit a 0, your count resets to zero. This naturally suggests a dynamic programming approach where we build upon previous counts.

For any cell containing a 1, the length of the consecutive 1s ending at that cell depends on the length of consecutive 1s ending at the previous cell in the same direction. This creates a recurrence relation:

• If the current cell is 1, we extend the line from the previous cell by 1
• If the current cell is 0, the line breaks and the count becomes 0

Since we need to find the longest line in any of the four directions (horizontal, vertical, diagonal, anti-diagonal), we need to track counts for all four directions simultaneously. Each direction has its own "previous cell":

• Horizontal line: previous cell is to the left (i, j-1)
• Vertical line: previous cell is above (i-1, j)
• Diagonal line: previous cell is top-left (i-1, j-1)
• Anti-diagonal line: previous cell is top-right (i-1, j+1)

The padding with extra rows and columns is a clever implementation detail to avoid boundary checks. By initializing the padded borders with 0s, we ensure that any line starting at the edge of the actual matrix begins with a count of 0+1=1, which is correct.

As we traverse the matrix once, we continuously update our running counts for all four directions at each cell, keeping track of the maximum seen so far. This gives us an efficient O(m*n) solution with a single pass through the matrix.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution implements dynamic programming using four 2D arrays to track consecutive 1s in each direction. Here's how the implementation works:

Data Structure Setup:

• Create four (m+2) x (n+2) arrays initialized with zeros: a, b, c, d
• The extra padding (adding 2 to dimensions) eliminates the need for boundary checking
• Each array represents one direction:
  • a: vertical lines
  • b: horizontal lines
  • c: diagonal lines (top-left to bottom-right)
  • d: anti-diagonal lines (top-right to bottom-left)

Core Algorithm:

1. Iterate through the original matrix using indices i from 1 to m and j from 1 to n
2. For each cell, check if mat[i-1][j-1] equals 1 (adjusting indices due to padding)
3. If it's a 1, update all four direction arrays using the recurrence relations:
   • a[i][j] = a[i-1][j] + 1 (extend vertical line from above)
   • b[i][j] = b[i][j-1] + 1 (extend horizontal line from left)
   • c[i][j] = c[i-1][j-1] + 1 (extend diagonal line from top-left)
   • d[i][j] = d[i-1][j+1] + 1 (extend anti-diagonal line from top-right)
4. Update the answer with the maximum of all four values and the current answer

Pattern Used: This follows the classic DP pattern where dp[i][j] depends on previously computed values. The state transition is straightforward:

• If current cell is 1: dp[current] = dp[previous] + 1
• If current cell is 0: dp[current] = 0 (implicitly handled by initialization)

Time and Space Complexity:

• Time: O(m * n) - single pass through the matrix
• Space: O(m * n) - four auxiliary arrays of size (m+2) x (n+2)

The elegance of this solution lies in processing all four directions simultaneously in a single pass, avoiding the need for multiple traversals or complex boundary conditions.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×3 matrix:

mat = [[0, 1, 1],
       [1, 1, 0],
       [1, 0, 1]]

Step 1: Initialize four padded arrays (5×5 with zeros)

a = b = c = d = 
[[0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0],
 [0, 0, 0, 0, 0]]

Step 2: Process each cell

Position (0,0) - mat value is 0:

• All arrays remain 0 at position [1][1]
• Current max = 0

Position (0,1) - mat value is 1:

• a[1][2] = a[0][2] + 1 = 0 + 1 = 1 (vertical)
• b[1][2] = b[1][1] + 1 = 0 + 1 = 1 (horizontal)
• c[1][2] = c[0][1] + 1 = 0 + 1 = 1 (diagonal)
• d[1][2] = d[0][3] + 1 = 0 + 1 = 1 (anti-diagonal)
• Current max = 1

Position (0,2) - mat value is 1:

• a[1][3] = a[0][3] + 1 = 0 + 1 = 1 (vertical)
• b[1][3] = b[1][2] + 1 = 1 + 1 = 2 (horizontal - extends from left!)
• c[1][3] = c[0][2] + 1 = 0 + 1 = 1 (diagonal)
• d[1][3] = d[0][4] + 1 = 0 + 1 = 1 (anti-diagonal)
• Current max = 2

Position (1,0) - mat value is 1:

• a[2][1] = a[1][1] + 1 = 0 + 1 = 1 (vertical)
• b[2][1] = b[2][0] + 1 = 0 + 1 = 1 (horizontal)
• c[2][1] = c[1][0] + 1 = 0 + 1 = 1 (diagonal)
• d[2][1] = d[1][2] + 1 = 1 + 1 = 2 (anti-diagonal - extends from top-right!)
• Current max = 2

Position (1,1) - mat value is 1:

• a[2][2] = a[1][2] + 1 = 1 + 1 = 2 (vertical - extends from above!)
• b[2][2] = b[2][1] + 1 = 1 + 1 = 2 (horizontal - extends from left!)
• c[2][2] = c[1][1] + 1 = 0 + 1 = 1 (diagonal)
• d[2][2] = d[1][3] + 1 = 1 + 1 = 2 (anti-diagonal - extends!)
• Current max = 2

Position (1,2) - mat value is 0:

• All values remain 0 at position [2][3]
• Current max = 2

Position (2,0) - mat value is 1:

• a[3][1] = a[2][1] + 1 = 1 + 1 = 2 (vertical - extends from above!)
• b[3][1] = b[3][0] + 1 = 0 + 1 = 1 (horizontal)
• c[3][1] = c[2][0] + 1 = 0 + 1 = 1 (diagonal)
• d[3][1] = d[2][2] + 1 = 2 + 1 = 3 (anti-diagonal - extends further!)
• Current max = 3

Final Answer: 3

The longest line is the anti-diagonal from position (0,1) → (1,0) → (2,0), which has length 3.

This example demonstrates how:

• Each direction tracks independently
• Counts extend when consecutive 1s are found
• The anti-diagonal direction found the longest line by building up counts: 1 → 2 → 3

Solution Implementation

Time and Space Complexity

The time complexity is O(m × n), where m is the number of rows and n is the number of columns in the matrix. This is because the algorithm uses two nested loops that iterate through each cell of the matrix exactly once (from row 1 to m and column 1 to n), performing constant-time operations for each cell.

The space complexity is O(m × n), where m and n are the number of rows and columns in the matrix, respectively. The algorithm creates four 2D arrays (a, b, c, and d), each of size (m + 2) × (n + 2). Since each array requires O((m + 2) × (n + 2)) space, which simplifies to O(m × n), and we have four such arrays, the total space complexity remains O(m × n).

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

Common Pitfalls

1. Index Confusion with Padding

The most common mistake is mishandling the index mapping between the original matrix and the padded DP arrays. Since the DP arrays have dimensions (m+2) x (n+2) while the original matrix is m x n, developers often make off-by-one errors when accessing elements.

Incorrect Implementation:

# Wrong: Forgetting to adjust indices
if mat[i][j] == 1:  # This will cause IndexError
    vertical[i][j] = vertical[i-1][j] + 1

Correct Implementation:

# Correct: Properly adjusting indices for padded arrays
if mat[i-1][j-1] == 1:  # Subtract 1 from both indices
    vertical[i][j] = vertical[i-1][j] + 1

2. Anti-Diagonal Direction Error

A frequent mistake occurs when updating the anti-diagonal direction. Since anti-diagonals go from top-right to bottom-left, the column index should increase (not decrease) when looking at the previous position.

Incorrect Implementation:

# Wrong: Using j-1 instead of j+1 for anti-diagonal
anti_diagonal[i][j] = anti_diagonal[i-1][j-1] + 1  # This tracks diagonal, not anti-diagonal

Correct Implementation:

# Correct: Previous position for anti-diagonal is at (i-1, j+1)
anti_diagonal[i][j] = anti_diagonal[i-1][j+1] + 1

3. Space Optimization Trap

Some developers attempt to optimize space by reusing arrays or using a single 3D array, but this can lead to incorrect results if not carefully implemented.

Problematic Optimization:

# Attempting to use a single array for multiple directions
dp = [[0] * (cols + 2) for _ in range(rows + 2)]
# This won't work because each direction needs independent tracking

Better Approach (if space optimization is needed):

# Use a 3D array with proper indexing
dp = [[[0] * 4 for _ in range(cols + 2)] for _ in range(rows + 2)]
# dp[i][j][0] for vertical, dp[i][j][1] for horizontal, etc.

4. Forgetting to Initialize Maximum Value

Starting with an uninitialized or incorrectly initialized maximum value can lead to wrong results, especially for empty matrices or matrices with all zeros.

Incorrect Implementation:

# Wrong: Not initializing or using wrong initial value
max_length = float('-inf')  # Problematic for all-zero matrices

Correct Implementation:

# Correct: Initialize to 0 to handle edge cases properly
max_length = 0

5. Boundary Checking Without Padding

If attempting to solve without padding, forgetting boundary checks leads to index out of bounds errors.

Alternative Solution Without Padding (requires careful boundary checking):

for i in range(rows):
    for j in range(cols):
        if mat[i][j] == 1:
            # Must check boundaries before accessing previous cells
            vertical[i][j] = (vertical[i-1][j] if i > 0 else 0) + 1
            horizontal[i][j] = (horizontal[i][j-1] if j > 0 else 0) + 1
            diagonal[i][j] = (diagonal[i-1][j-1] if i > 0 and j > 0 else 0) + 1
            anti_diagonal[i][j] = (anti_diagonal[i-1][j+1] if i > 0 and j < cols-1 else 0) + 1

The padding approach in the original solution elegantly avoids these boundary checks, making the code cleaner and less error-prone.