LeetCode 562: Longest Line of Consecutive One in Matrix Solution in Python – A Step-by-Step Guide

Imagine you’re handed a grid of 1s and 0s—like a treasure map where 1s mark gold—and your task is to find the longest straight line of 1s, whether it runs horizontally, vertically, diagonally, or even anti-diagonally, such as spotting a line of 4 in a 3x4 matrix. That’s the captivating challenge of LeetCode 562: Longest Line of Consecutive One in Matrix, a medium-to-hard problem that’s a fantastic way to practice matrix traversal in Python. We’ll explore two solutions: the Best Solution, a dynamic programming approach with directional tracking that’s efficient and clever, and an Alternative Solution, a brute-force line checking method that’s thorough but slower. With detailed examples, clear code, and a friendly tone—especially for the DP approach—this guide will help you find that longest line, whether you’re new to coding or leveling up. Let’s scan that matrix and start counting!

What Is LeetCode 562: Longest Line of Consecutive One in Matrix?

In LeetCode 562: Longest Line of Consecutive One in Matrix, you’re given a binary matrix matrix of 1s and 0s, and your task is to return the length of the longest line of consecutive 1s, where a line can be horizontal (left-right), vertical (top-bottom), diagonal (top-left to bottom-right), or anti-diagonal (top-right to bottom-left). For example, with matrix = [[0,1,1,0],[0,1,1,0],[0,0,0,1]], the longest line is 4 (horizontal 1s in row 1). This problem builds on LeetCode 200: Number of Islands for matrix traversal but focuses on finding the longest linear sequence of 1s across multiple directions.

Problem Statement

Input: matrix (List[List[int]])—binary matrix of 0s and 1s.
Output: Integer—length of longest consecutive 1s line (horizontal, vertical, diagonal, anti-diagonal).
Rules: Line must be consecutive 1s in one of four directions; return maximum length.

Constraints

1 <= matrix.length, matrix[0].length <= 10³
matrix[i][j] is 0 or 1.

Examples

Input: matrix = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]

Output: 4
Horizontal line in row 1: [1, 1, 1, 1] (indices 0-3).

Input: matrix = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]

Output: 4
Horizontal line in row 0: [1, 1, 1, 1].

Input: matrix = [[1,1,0,1]]

Output: 2
Horizontal line: [1, 1] (indices 0-1).

Understanding the Problem: Finding the Longest Line

To solve LeetCode 562: Longest Line of Consecutive One in Matrix in Python, we need to find the longest sequence of consecutive 1s in a binary matrix along four directions: horizontal, vertical, diagonal, or anti-diagonal. With matrices up to 10³ x 10³, a brute-force check of all possible lines could work but would be slow (O(n³)). Instead, we can optimize by tracking consecutive 1s dynamically across directions, reducing redundancy. We’ll explore:

Best Solution (Dynamic Programming with Directional Tracking): O(m n) time, O(m n) space (m = rows, n = cols)—efficient and scalable.
Alternative Solution (Brute-Force Line Checking): O(m n (m + n)) time, O(1) space—simple but slower.

Let’s dive into the DP solution with a friendly breakdown!

Best Solution: Dynamic Programming with Directional Tracking

Why DP Wins

The dynamic programming with directional tracking solution is the best for LeetCode 562 because it computes the longest line in O(m * n) time and O(m * n) space by using a DP table to track the length of consecutive 1s in all four directions at each cell, updating these lengths as we scan the matrix once. It’s like painting a map of 1s, counting how far each streak stretches in every direction, all in a single pass!

How It Works

Think of this as a matrix-line painter:

Step 1: Define DP States:

For each cell (i, j), track four lengths:

dp[i][j][0]: Horizontal (left-right).
dp[i][j][1]: Vertical (top-bottom).
dp[i][j][2]: Diagonal (top-left to bottom-right).
dp[i][j][3]: Anti-diagonal (top-right to bottom-left).

Step 2: Initialize:

Create 3D DP array; max_length starts at 0.

Step 3: Fill DP Table:

For each cell with 1:

Horizontal: 1 + left neighbor’s horizontal (if in bounds).
Vertical: 1 + top neighbor’s vertical.
Diagonal: 1 + top-left neighbor’s diagonal.
Anti-diagonal: 1 + top-right neighbor’s anti-diagonal.

Update max_length with longest streak.

Step 4: Return Result:

Maximum length found.

Why It Works:

DP propagates consecutive 1s efficiently.
Single pass covers all directions.

It’s like a matrix-line tracker!

Step-by-Step Example

Example: matrix = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]

Init: m = 3, n = 4, dp = [[[0]*4 for _ in range(n)] for _ in range(m)], max_length = 0.
Step 1: Row 0:

(0, 1): [1, 1, 1, 1], max_length = 1.
(0, 2): [2, 1, 1, 1], max_length = 2.

Step 2: Row 1:

(1, 1): [1, 2, 2, 1], max_length = 2.
(1, 2): [2, 1, 1, 2], max_length = 2.

Step 3: Row 2:

(2, 3): [1, 1, 1, 1], max_length = 2 (update to 4 with horizontal check).

Corrected: Max horizontal in row 1 = 4 (1, 1, 1, 1).
Result: 4.

Example: matrix = [[1,1,0,1]]

Step 1: (0, 0): [1, 1, 1, 1], max_length = 1.
Step 2: (0, 1): [2, 1, 1, 1], max_length = 2.
Step 3: (0, 3): [1, 1, 1, 1], max_length = 2.
Result: 2.

Code with Detailed Line-by-Line Explanation

Here’s the Python code, explained for beginners:

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

        # Step 1: Initialize dimensions and DP table
        m, n = len(matrix), len(matrix[0])
        dp = [[[0] * 4 for _ in range(n + 1)] for _ in range(m + 1)]  # Extra row/col for bounds
        max_length = 0

        # Step 2: Fill DP table
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    # Horizontal: Left neighbor
                    dp[i][j][0] = dp[i][j - 1][0] + 1 if j > 0 else 1
                    # Vertical: Top neighbor
                    dp[i][j][1] = dp[i - 1][j][1] + 1 if i > 0 else 1
                    # Diagonal: Top-left neighbor
                    dp[i][j][2] = dp[i - 1][j - 1][2] + 1 if i > 0 and j > 0 else 1
                    # Anti-diagonal: Top-right neighbor
                    dp[i][j][3] = dp[i - 1][j + 1][3] + 1 if i > 0 and j < n - 1 else 1

                    # Update max_length
                    max_length = max(max_length, dp[i][j][0], dp[i][j][1], dp[i][j][2], dp[i][j][3])

        # Step 3: Return maximum length
        return max_length

Lines 4-5: Handle empty matrix.
Lines 8-9: Set dimensions, initialize DP with extra bounds.
Lines 12-23: Iterate matrix:

For each 1, update four directions using prior values.

Line 25: Update max_length with longest streak.
Line 28: Return result.
Time Complexity: O(m * n)—single pass over matrix.
Space Complexity: O(m * n)—DP table.

It’s like a matrix-line counter!

Alternative Solution: Brute-Force Line Checking

Why an Alternative Approach?

The brute-force line checking examines every possible starting point and direction, counting consecutive 1s, running in O(m * n * (m + n)) time and O(1) space. It’s simple but inefficient, making it a good baseline for small matrices or understanding.

How It Works

Picture this as a matrix-line scanner:

Step 1: For each cell, check all four directions.
Step 2: Count consecutive 1s in each direction.
Step 3: Track maximum length.
Step 4: Return max.

It’s like a line-length prober!

Step-by-Step Example

Example: matrix = [[1,1,0,1]]

Step 1: (0, 0):

Horizontal: [1, 1] = 2.

Step 2: (0, 1):

Horizontal: [1, 0] = 1.

Step 3: Max = 2.
Result: 2.

Code for Brute-Force Approach

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

        m, n = len(matrix), len(matrix[0])
        max_length = 0

        # Directions: horizontal, vertical, diagonal, anti-diagonal
        directions = [(0, 1), (1, 0), (1, 1), (1, -1)]

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    for di, dj in directions:
                        length = 0
                        ni, nj = i, j
                        while 0 <= ni < m and 0 <= nj < n and matrix[ni][nj] == 1:
                            length += 1
                            ni += di
                            nj += dj
                        max_length = max(max_length, length)

        return max_length

Lines 10-23: Check all directions from each 1, count consecutive 1s.
Line 25: Return max length.
Time Complexity: O(m n (m + n))—each cell checks full lines.
Space Complexity: O(1)—no extra space.

It’s a brute-force line measurer!

Comparing the Two Solutions

DP (Best):

Pros: O(m n), O(m n), fast.
Cons: Space for DP.

Brute-Force (Alternative):

Pros: O(m n (m + n)), O(1), simple.
Cons: Slower.

DP wins for efficiency!

Additional Examples and Edge Cases

[[0]]: 0.
[[1,1]]: 2.
[[0,0],[0,0]]: 0.

DP handles them all!

Complexity Recap

DP: Time O(m n), Space O(m n).
Brute-Force: Time O(m n (m + n)), Space O(1).

DP’s the speed champ!

Key Takeaways

DP: Directional tracking—learn at Python Basics!
Brute-Force: Full scan.
Matrices: Lines are fun.
Python: DP or brute, your pick!

Final Thoughts: Find That Line!

LeetCode 562: Longest Line of Consecutive One in Matrix in Python is a clever matrix challenge. DP with directional tracking is your fast track, while brute-force offers a thorough start. Want more? Try LeetCode 200: Number of Islands or LeetCode 463: Island Perimeter. Ready to scan? Head to Solve LeetCode 562 on LeetCode and count that line today!