LeetCode 562: Longest Line of Consecutive One in Matrix

A clear explanation of Longest Line of Consecutive One in Matrix using dynamic programming over four directions.

leetcodearraymatrixdynamic-programming

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:

Direction Meaning
Horizontal Left to right
Vertical Top to bottom
Diagonal Top-left to bottom-right
Anti-diagonal Top-right to bottom-left

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

Item Meaning
Input A binary matrix mat
Output Length of the longest consecutive line of 1 values
Allowed directions Horizontal, vertical, diagonal, anti-diagonal
Cell values Only 0 and 1

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):

Direction Previous cell
Horizontal (i, j - 1)
Vertical (i - 1, j)
Diagonal (i - 1, j - 1)
Anti-diagonal (i - 1, j + 1)

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:

State Meaning
dp[i][j][0] Horizontal length ending at (i, j)
dp[i][j][1] Vertical length ending at (i, j)
dp[i][j][2] Diagonal length ending at (i, j)
dp[i][j][3] Anti-diagonal length ending at (i, j)

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.

Metric Value Why
Time O(mn) Each cell is processed once
Space O(mn) The DP table stores four values per cell

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()
Test Why
Main sample Checks diagonal and normal mixed matrix
[[0]] Single zero
[[1]] Single one
One row of ones Horizontal line
One column of ones Vertical line
Main diagonal Diagonal direction
Anti-diagonal Anti-diagonal direction