LeetCode 562 - Longest Line of Consecutive One in Matrix

The problem gives us a binary matrix mat of size m x n, where every cell contains either 0 or 1. We need to find the length of the longest consecutive sequence of 1s that appears in any of four directions: 1. Horizontal, from left to right 2. Vertical, from top to bottom 3.

leetcodemediumarraydynamic-programmingmatrix

LeetCode Problem 562

Difficulty: 🟡 Medium
Topics: Array, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem gives us a binary matrix mat of size m x n, where every cell contains either 0 or 1. We need to find the length of the longest consecutive sequence of 1s that appears in any of four directions:

  1. Horizontal, from left to right
  2. Vertical, from top to bottom
  3. Diagonal, from top-left to bottom-right
  4. Anti-diagonal, from top-right to bottom-left

The result is the maximum number of consecutive 1s found along any valid line.

For example, consider:

[
  [0,1,1,0],
  [0,1,1,0],
  [0,0,0,1]
]

The longest consecutive line is the diagonal:

1
  1
    1

which has length 3.

The constraints are important:

  • 1 <= m, n <= 10^4
  • 1 <= m * n <= 10^4

Although one dimension may be large, the total number of cells is at most 10^4. This means an O(m * n) or O(m * n * constant) solution is efficient enough.

A naive solution that repeatedly scans in every direction from every cell could still work within these constraints, but it performs redundant work. A dynamic programming approach avoids recomputation and gives a cleaner and more scalable solution.

Some important edge cases include:

  • A matrix containing only 0s, where the answer should be 0
  • A matrix containing only 1s, where the answer could be an entire row, column, or diagonal
  • Single row matrices
  • Single column matrices
  • Cases where the longest line is diagonal or anti-diagonal instead of horizontal or vertical
  • Sparse matrices where isolated 1s appear without forming longer chains

Understanding these cases helps ensure we correctly handle boundaries and directional transitions.

Approaches

Brute Force Approach

The brute force idea is straightforward. For every cell containing 1, we attempt to extend a line in all four directions:

  • Right
  • Down
  • Diagonal down-right
  • Diagonal down-left

For each direction, we keep moving while the cells remain inside the matrix and contain 1.

This approach is correct because every possible valid line begins at some cell, and checking all directions guarantees we eventually discover the longest one.

However, the same sequences get recomputed many times. Suppose a row contains 100 consecutive 1s. Starting from each cell, we repeatedly scan the remaining suffix of that row. This creates unnecessary repeated work.

In the worst case, each cell may trigger scans of length O(max(m, n)), giving a total complexity close to:

O(m * n * max(m, n))

This is avoidable.

Optimal Dynamic Programming Approach

The key observation is that the length of a consecutive line ending at a cell depends only on neighboring cells in the same direction.

For a cell (r, c) containing 1:

  • Horizontal count depends on (r, c-1)
  • Vertical count depends on (r-1, c)
  • Diagonal count depends on (r-1, c-1)
  • Anti-diagonal count depends on (r-1, c+1)

This creates a natural dynamic programming transition.

Instead of recomputing line lengths repeatedly, we store the length of consecutive 1s ending at each cell for all four directions.

If mat[r][c] == 1, then:

horizontal = left + 1
vertical = up + 1
diagonal = upper-left + 1
anti-diagonal = upper-right + 1

This allows every cell to be processed once, leading to an efficient O(m * n) solution.

Approach Time Complexity Space Complexity Notes
Brute Force O(m * n * max(m, n)) O(1) Repeatedly scans the same lines
Optimal O(m * n) O(m * n) Dynamic programming stores directional lengths

Algorithm Walkthrough

  1. Create a DP table where each cell stores four values:
  • Horizontal line length
  • Vertical line length
  • Diagonal line length
  • Anti-diagonal line length

We use these values because the problem asks us to track consecutive 1s in four different directions independently. 2. Initialize a variable max_length = 0.

This variable keeps track of the longest valid line found so far. 3. Traverse the matrix row by row and column by column.

Processing row-major order ensures that all previously needed neighboring states have already been computed. 4. If the current cell contains 0, skip it.

A line of consecutive 1s cannot continue through a 0. 5. If the current cell contains 1, compute the four directional values:

  • Horizontal:

  • Start with 1

  • Add the horizontal value from the left neighbor if it exists

  • Vertical:

  • Start with 1

  • Add the vertical value from the upper neighbor if it exists

  • Diagonal:

  • Start with 1

  • Add the diagonal value from the upper-left neighbor if it exists

  • Anti-diagonal:

  • Start with 1

  • Add the anti-diagonal value from the upper-right neighbor if it exists

  1. Store these four values in the DP table.

Each value represents the longest consecutive line ending exactly at the current cell in that direction. 7. Update max_length using the maximum among the four computed values. 8. After processing all cells, return max_length.

Why it works

The dynamic programming recurrence works because every consecutive line ending at a cell must extend from a neighboring cell in the same direction.

For example, a horizontal line ending at (r, c) can only come from (r, c-1). If the left neighbor already represents the length of the longest horizontal chain ending there, adding 1 correctly extends the chain.

The same logic applies independently to vertical, diagonal, and anti-diagonal directions. Since every cell is processed after its required neighbors, all DP states are available when needed.

Therefore, the algorithm correctly computes the longest consecutive line in all four directions.

Python Solution

from typing import List

class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])

        # dp[r][c] = [horizontal, vertical, diagonal, anti_diagonal]
        dp = [[[0] * 4 for _ in range(cols)] for _ in range(rows)]

        max_length = 0

        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    continue

                # Horizontal
                dp[r][c][0] = 1
                if c > 0:
                    dp[r][c][0] += dp[r][c - 1][0]

                # Vertical
                dp[r][c][1] = 1
                if r > 0:
                    dp[r][c][1] += dp[r - 1][c][1]

                # Diagonal
                dp[r][c][2] = 1
                if r > 0 and c > 0:
                    dp[r][c][2] += dp[r - 1][c - 1][2]

                # Anti-diagonal
                dp[r][c][3] = 1
                if r > 0 and c < cols - 1:
                    dp[r][c][3] += dp[r - 1][c + 1][3]

                max_length = max(max_length, *dp[r][c])

        return max_length

The implementation begins by determining the matrix dimensions and allocating a three-dimensional DP table.

Each cell stores four integers representing the lengths of consecutive 1s ending at that position in four directions.

During traversal:

  • Cells containing 0 are skipped immediately because they cannot contribute to a line.
  • Cells containing 1 compute each directional value independently.
  • Boundary checks ensure we do not access invalid indices.

For example, horizontal computation uses:

dp[r][c][0] += dp[r][c - 1][0]

This extends the left neighbor's horizontal chain.

Similarly:

  • Vertical extends upward
  • Diagonal extends upper-left
  • Anti-diagonal extends upper-right

After computing the four values, we update the global maximum.

The algorithm processes each cell exactly once, making it highly efficient.

Go Solution

func longestLine(mat [][]int) int {
	rows := len(mat)
	cols := len(mat[0])

	// dp[r][c][0] = horizontal
	// dp[r][c][1] = vertical
	// dp[r][c][2] = diagonal
	// dp[r][c][3] = anti-diagonal
	dp := make([][][]int, rows)

	for r := 0; r < rows; r++ {
		dp[r] = make([][]int, cols)
		for c := 0; c < cols; c++ {
			dp[r][c] = make([]int, 4)
		}
	}

	maxLength := 0

	for r := 0; r < rows; r++ {
		for c := 0; c < cols; c++ {

			if mat[r][c] == 0 {
				continue
			}

			// Horizontal
			dp[r][c][0] = 1
			if c > 0 {
				dp[r][c][0] += dp[r][c-1][0]
			}

			// Vertical
			dp[r][c][1] = 1
			if r > 0 {
				dp[r][c][1] += dp[r-1][c][1]
			}

			// Diagonal
			dp[r][c][2] = 1
			if r > 0 && c > 0 {
				dp[r][c][2] += dp[r-1][c-1][2]
			}

			// Anti-diagonal
			dp[r][c][3] = 1
			if r > 0 && c < cols-1 {
				dp[r][c][3] += dp[r-1][c+1][3]
			}

			for k := 0; k < 4; k++ {
				if dp[r][c][k] > maxLength {
					maxLength = dp[r][c][k]
				}
			}
		}
	}

	return maxLength
}

The Go implementation closely mirrors the Python solution.

Since Go does not support dynamic multidimensional arrays as conveniently as Python, we explicitly allocate the three-dimensional slice structure.

Unlike Python's max() function, Go requires manual comparison when updating the maximum value.

There are no integer overflow concerns because the maximum possible line length is at most 10^4.

Worked Examples

Example 1

Input:

[
  [0,1,1,0],
  [0,1,1,0],
  [0,0,0,1]
]

We track four values per cell:

[horizontal, vertical, diagonal, anti-diagonal]

Row 0

Cell Value DP State
(0,0) 0 skipped
(0,1) 1 [1,1,1,1]
(0,2) 1 [2,1,1,1]
(0,3) 0 skipped

Current maximum: 2

Row 1

Cell Value DP State
(1,0) 0 skipped
(1,1) 1 [1,2,1,2]
(1,2) 1 [2,2,2,1]
(1,3) 0 skipped

Current maximum: 2

Row 2

Cell Value DP State
(2,0) 0 skipped
(2,1) 0 skipped
(2,2) 0 skipped
(2,3) 1 [1,1,3,1]

The diagonal length becomes 3, which is the final answer.

Output:

3

Example 2

Input:

[
  [1,1,1,1],
  [0,1,1,0],
  [0,0,0,1]
]

Row 0

Cell DP State
(0,0) [1,1,1,1]
(0,1) [2,1,1,1]
(0,2) [3,1,1,1]
(0,3) [4,1,1,1]

Maximum becomes 4.

Remaining Rows

No later sequence exceeds length 4.

Final answer:

4

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Every cell is processed once
Space O(m * n) DP table stores four values per cell

The algorithm performs constant work for each matrix cell. Since there are m * n cells total, the runtime is linear in the matrix size.

The DP table stores four integers for every cell, which also scales linearly with the number of cells.

Test Cases

from typing import List

class Solution:
    def longestLine(self, mat: List[List[int]]) -> int:
        rows = len(mat)
        cols = len(mat[0])

        dp = [[[0] * 4 for _ in range(cols)] for _ in range(rows)]

        max_length = 0

        for r in range(rows):
            for c in range(cols):
                if mat[r][c] == 0:
                    continue

                dp[r][c][0] = 1 + (dp[r][c - 1][0] if c > 0 else 0)
                dp[r][c][1] = 1 + (dp[r - 1][c][1] if r > 0 else 0)
                dp[r][c][2] = 1 + (
                    dp[r - 1][c - 1][2] if r > 0 and c > 0 else 0
                )
                dp[r][c][3] = 1 + (
                    dp[r - 1][c + 1][3]
                    if r > 0 and c < cols - 1
                    else 0
                )

                max_length = max(max_length, *dp[r][c])

        return max_length

sol = Solution()

assert sol.longestLine(
    [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
) == 3  # diagonal line

assert sol.longestLine(
    [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
) == 4  # horizontal line

assert sol.longestLine(
    [[0]]
) == 0  # single zero cell

assert sol.longestLine(
    [[1]]
) == 1  # single one cell

assert sol.longestLine(
    [[1,1,1,1,1]]
) == 5  # single row

assert sol.longestLine(
    [[1],[1],[1],[1]]
) == 4  # single column

assert sol.longestLine(
    [[1,0,0],[0,1,0],[0,0,1]]
) == 3  # diagonal only

assert sol.longestLine(
    [[0,0,1],[0,1,0],[1,0,0]]
) == 3  # anti-diagonal only

assert sol.longestLine(
    [[0,0],[0,0]]
) == 0  # all zeros

assert sol.longestLine(
    [[1,1],[1,1]]
) == 2  # multiple equal answers
Test Why
Example 1 Validates diagonal detection
Example 2 Validates horizontal detection
Single zero cell Smallest matrix with no valid line
Single one cell Smallest matrix with valid line
Single row Tests horizontal accumulation
Single column Tests vertical accumulation
Main diagonal Tests diagonal transitions
Anti-diagonal Tests anti-diagonal transitions
All zeros Ensures algorithm handles absence of lines
All ones 2x2 Tests multiple directions with equal lengths

Edge Cases

Matrix Containing Only Zeroes

A matrix such as:

[
  [0,0],
  [0,0]
]

can expose bugs where algorithms incorrectly initialize the answer to 1 or attempt to extend nonexistent lines.

Our implementation handles this correctly because we only compute DP states when a cell contains 1. The maximum remains initialized at 0.

Single Row or Single Column

Matrices with only one row or one column are important because some directional neighbors do not exist.

For example:

[[1,1,1,1]]

or

[
 [1],
 [1],
 [1]
]

Without careful boundary checks, accessing upper or left neighbors may cause index errors.

Our implementation explicitly checks bounds before using neighboring DP values.

Anti-Diagonal Sequences

Anti-diagonal handling is easy to implement incorrectly because it depends on the upper-right neighbor.

Example:

[
  [0,0,1],
  [0,1,0],
  [1,0,0]
]

The correct answer is 3.

The implementation correctly uses:

dp[r - 1][c + 1][3]

which tracks anti-diagonal chains ending at the upper-right position. Boundary checks ensure we never access invalid columns.