Domain 2MediumCORE

Longest Line of Consecutive One in Matrix

We are given a binary matrix M containing only 0s and 1s. Our goal is to find the maximum number of consecutive 1s in any valid line direction: horizontal (row), vertical (column), diagonal (), or anti-diagonal (/).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

562. Longest Line of Consecutive One in Matrix

Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 46.2%


Problem Breakdown

We are given a binary matrix M containing only 0s and 1s. Our goal is to find the maximum number of consecutive 1s in any valid line direction: horizontal (row), vertical (column), diagonal (\), or anti-diagonal (/).

Inputs: A list of lists representing the grid, where each inner list has equal length C. Outputs: An integer representing the longest streak found.

Constraints & Edge Cases:

  1. Empty Matrix: If input is empty (0 rows or cols), return 0 immediately to avoid index errors.
  2. All Zeros/Ones: The logic must handle a grid of all zeros (returning 0) and all ones (returning min(R, C)).
  3. Dimensions: Rows (RR) and Columns (CC) can vary independently.
  4. Memory Limit: With up to 10410^4 elements total, an auxiliary space of O(R⋅C)O(R \cdot C) is perfectly acceptable (typically < few MBs), so we prioritize clarity over aggressive memory optimization unless requested.

Intuition

A brute-force approach would be to iterate through every cell and check all four directions starting from that point until a 0 or boundary is hit.

  • Complexity: For each of the R⋅CR \cdot C cells, traversing up to length min⁡(R,C)\min(R,C) in worst case leads to roughly O((RC)2)O((RC)^2). Given constraints (10410^4 elements), this might pass but risks TLE on larger inputs or dense matrices.
  • Optimization: We can use Dynamic Programming (DP). Notice that if matrix[i][j] == 1, it extends the line ending at (i-1, j) vertically, (i, j-1) horizontally, etc. If we store how many consecutive ones ended at each cell for all four directions as we traverse once, we can compute the answer in a single pass.
  • Key Insight: The state of any direction depends only on its immediate predecessor within that same line type (e.g., vertical count at (r,c) is 1 + vertical count at (r-1,c)). This allows us to update counts incrementally without re-scanning lines from scratch.

Approach

We will iterate through the matrix row by row, column by column (O(R⋅C)O(R \cdot C) time). For each cell containing a 0, we reset all direction counters for that position (effectively treating it as length 0). If the cell is a 1:

  1. Horizontal: h[r][c] = h[r][c-1] + 1 (if valid column index exists).
  2. Vertical: v[r][c] = v[r-1][c] + 1.
  3. Diagonal: d[r][c] = d[r-1][c-1] + 1.
  4. Anti-Diagonal: ad[r][c] = ad[r-1][c+1] + 1.

We maintain a global maximum variable updated at every step where we encounter a 1. To handle boundary conditions (like the first row or column), we check if indices are valid before accessing neighbors; otherwise, the count starts fresh at 1 for that cell. We use four separate DP tables to store these counts explicitly rather than modifying the input matrix to avoid side effects and ensure clarity during explanation.

Complexity Analysis

  • Time: O(R⋅C)O(R \cdot C). We visit each element exactly once performing constant-time arithmetic operations (4 lookups + 1 assignment).
  • Space: O(R⋅C)O(R \cdot C) for the four auxiliary DP tables (h, v, d, ad). This is proportional to input size. Note: Space can be optimized to O(C)O(C) by only storing previous row states, but given constraints (N∗M≤104N*M \le 10^4), this optimization adds complexity without significant benefit for the interview context unless memory limits are tight.

Solution

class Solution:
    def longestLine(self, matrix):
        if not matrix or not matrix[0]:
            return 0
        
        rows = len(matrix)
        cols = len(matrix[0])
        
        # Initialize DP tables for horizontal (h), vertical (v), 
        # diagonal (d), and anti-diagonal (ad).
        h, v, d, ad = [row[:] * 1] + [[0]*cols for _ in range(rows)]

        max_len = 0
        
        for r in range(rows):
            for c in range(cols):
                if matrix[r][c] == 1:
                    # Horizontal depends on left neighbor (same row)
                    h[r][c] = h[r][c-1] + 1 if c > 0 else 1
                    
                    # Vertical depends on top neighbor (previous row, same col)
                    v[r][c] = v[r-1][c] + 1 if r > 0 else 1
                    
                    # Diagonal depends on top-left neighbor
                    d[r][c] = d[r-1][c-1] + 1 if r > 0 and c > 0 else 1
                    
                    # Anti-diagonal depends on top-right neighbor
                    ad[r][c] = ad[r-1][c+1] + 1 if r > 0 and c < cols - 1 else 1
                    
                    max_len = max(max_len, h[r][c], v[r][c], d[r][c], ad[r][c])
                # If matrix[r][c] == 0, all counters remain 0 (default)

        return max_len

Edge Cases Handled

  • Empty Matrix: Checked at the start (if not matrix or not matrix[0]:). Returns 0.
  • Single Element ‘1’: Loops run once; neighbors checks fail, sets count to 1. Max len becomes 1. Correct.
  • Boundary Rows/Cols (Row 0, Col 0): Conditional logic (if c > 0, etc.) ensures we don’t access out-of-bounds indices for horizontal/diagonal dependencies when at the edge of the matrix.
  • All Zeros: max_len remains initialized to 0. Correctly returns 0.