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

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

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

## Examples

Example:

```python
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:

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

So the answer is:

```python
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:

```python
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:

```python
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

```python
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:

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

When the current cell is `0`, we skip it:

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

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

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

A vertical line extends from above:

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

A diagonal line extends from the upper-left cell:

```python
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:

```python
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:

```python
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.

```python
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

```python
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 |