LeetCode 562: Longest Line of Consecutive One in Matrix

Problem Restatement

We are given a binary matrix mat.

Each cell contains either 0 or 1.

We need to find the length of the longest line of consecutive 1 values.

The line may go in one of four directions:

Return the maximum length among all such lines.

The original problem states that the number of elements in the matrix does not exceed 10000.

Input and Output

Example function shape:

def longestLine(mat: list[list[int]]) -> int:
    ...

Examples

Example:

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

The longest line has length 3.

One such line is the diagonal:

mat[0][1] = 1
mat[1][2] = 1
mat[2][3] = 1

So the answer is:

3

First Thought: Start From Every Cell

A direct solution is to start from every cell containing 1.

From that cell, try walking in all four directions and count how many consecutive 1 values appear.

This works, but it repeats many checks.

For example, in a long horizontal line of 1 values, starting from each cell recounts much of the same line again.

We need to reuse previous counts.

Key Insight

For each cell, if the cell is 1, the longest line ending at that cell can be computed from a neighboring cell.

For a cell (i, j):

If mat[i][j] == 1, then:

horizontal = previous_horizontal + 1
vertical = previous_vertical + 1
diagonal = previous_diagonal + 1
anti_diagonal = previous_anti_diagonal + 1

If mat[i][j] == 0, all four counts ending at that cell are 0.

This is dynamic programming.

Dynamic Programming State

Let:

dp[i][j][0]

be the horizontal line length of consecutive 1 values ending at (i, j).

Similarly:

For every 1 cell, update these four values and update the answer.

Algorithm

1. Let m = len(mat) and n = len(mat[0]).
2. Create a DP table of shape m x n x 4.
3. Initialize ans = 0.
4. For each cell (i, j):
   1. If mat[i][j] == 0, skip it.
   2. Set the horizontal count from the left neighbor.
   3. Set the vertical count from the upper neighbor.
   4. Set the diagonal count from the upper-left neighbor.
   5. Set the anti-diagonal count from the upper-right neighbor.
   6. Update ans.

Correctness

For any cell containing 0, no line of consecutive 1 values can end at that cell. The algorithm correctly leaves all four counts as 0.

For any cell (i, j) containing 1, a horizontal line ending at (i, j) either has length 1, or it extends a horizontal line ending at (i, j - 1). Therefore, the horizontal recurrence is correct.

The same reasoning applies to the other directions. A vertical line extends from (i - 1, j), a diagonal line extends from (i - 1, j - 1), and an anti-diagonal line extends from (i - 1, j + 1).

Every valid line of consecutive 1 values has a final cell in its direction. When the algorithm processes that final cell, the DP value for that direction equals the length of the line. Since the algorithm takes the maximum over all cells and all four directions, it returns the length of the longest valid line.

Complexity

Let m be the number of rows and n be the number of columns.

Implementation

class Solution:
    def longestLine(self, mat: list[list[int]]) -> int:
        if not mat or not mat[0]:
            return 0

        m = len(mat)
        n = len(mat[0])

        dp = [[[0] * 4 for _ in range(n)] for _ in range(m)]
        ans = 0

        for i in range(m):
            for j in range(n):
                if mat[i][j] == 0:
                    continue

                dp[i][j][0] = dp[i][j - 1][0] + 1 if j > 0 else 1
                dp[i][j][1] = dp[i - 1][j][1] + 1 if i > 0 else 1
                dp[i][j][2] = dp[i - 1][j - 1][2] + 1 if i > 0 and j > 0 else 1
                dp[i][j][3] = dp[i - 1][j + 1][3] + 1 if i > 0 and j + 1 < n else 1

                ans = max(ans, max(dp[i][j]))

        return ans

Code Explanation

The DP table stores four counts for every cell:

dp = [[[0] * 4 for _ in range(n)] for _ in range(m)]

When the current cell is 0, we skip it:

if mat[i][j] == 0:
    continue

A horizontal line ending at (i, j) extends from the left:

dp[i][j][0] = dp[i][j - 1][0] + 1 if j > 0 else 1

A vertical line extends from above:

dp[i][j][1] = dp[i - 1][j][1] + 1 if i > 0 else 1

A diagonal line extends from the upper-left cell:

dp[i][j][2] = dp[i - 1][j - 1][2] + 1 if i > 0 and j > 0 else 1

An anti-diagonal line extends from the upper-right cell:

dp[i][j][3] = dp[i - 1][j + 1][3] + 1 if i > 0 and j + 1 < n else 1

After computing the four values, we update the answer:

ans = max(ans, max(dp[i][j]))

Space-Optimized Version

We can reduce memory by keeping only the previous row and the current row.

This works because each DP value only depends on:

1. The current row’s left cell.
2. The previous row.
3. The previous row’s left or right neighbor.

class Solution:
    def longestLine(self, mat: list[list[int]]) -> int:
        if not mat or not mat[0]:
            return 0

        m = len(mat)
        n = len(mat[0])

        prev = [[0] * 4 for _ in range(n)]
        ans = 0

        for i in range(m):
            curr = [[0] * 4 for _ in range(n)]

            for j in range(n):
                if mat[i][j] == 0:
                    continue

                curr[j][0] = curr[j - 1][0] + 1 if j > 0 else 1
                curr[j][1] = prev[j][1] + 1
                curr[j][2] = prev[j - 1][2] + 1 if j > 0 else 1
                curr[j][3] = prev[j + 1][3] + 1 if j + 1 < n else 1

                ans = max(ans, max(curr[j]))

            prev = curr

        return ans

This version uses O(n) space.

Testing

def run_tests():
    s = Solution()

    assert s.longestLine([
        [0, 1, 1, 0],
        [0, 1, 1, 0],
        [0, 0, 0, 1],
    ]) == 3

    assert s.longestLine([[0]]) == 0
    assert s.longestLine([[1]]) == 1

    assert s.longestLine([
        [1, 1, 1, 1],
    ]) == 4

    assert s.longestLine([
        [1],
        [1],
        [1],
    ]) == 3

    assert s.longestLine([
        [1, 0, 0],
        [0, 1, 0],
        [0, 0, 1],
    ]) == 3

    assert s.longestLine([
        [0, 0, 1],
        [0, 1, 0],
        [1, 0, 0],
    ]) == 3

    print("all tests passed")

run_tests()