We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Line of Consecutive One in Matrix

Number: 562

Difficulty: Medium

Paid? Yes

Companies: Google

Problem Description

Given an m x n binary matrix, the task is to find the length of the longest line of consecutive 1s in the matrix. The consecutive line may be horizontal, vertical, diagonal, or anti-diagonal.

Key Insights

  • The problem involves scanning the matrix in four different directions for each cell that contains a 1.
  • Use dynamic programming to store the count of consecutive ones ending at each cell in each direction.
  • Update counts based on previously computed adjacent cells, which avoids redundant computations.
  • The four directions to consider are:
    • Horizontal: left to right
    • Vertical: top to bottom
    • Diagonal: top-left to bottom-right
    • Anti-diagonal: top-right to bottom-left

Space and Time Complexity

Time Complexity: O(m * n) where m and n are the dimensions of the matrix. Space Complexity: O(m * n) if using auxiliary DP arrays for each direction, but can be optimized to O(n) per direction when processing row by row.

Solution

We solve the problem using a dynamic programming approach that maintains four auxiliary arrays (or matrices) for the number of consecutive ones in horizontal, vertical, diagonal, and anti-diagonal directions that end at the current cell. For a cell at position (i, j):

  • For the horizontal direction, if the current cell has a 1, add 1 to the count from its left (i, j-1).
  • For the vertical direction, add 1 to the count from cell (i-1, j).
  • For the diagonal direction, add 1 to the count from the cell (i-1, j-1).
  • For the anti-diagonal direction, add 1 to the count from the cell (i-1, j+1). By tracking the maximum value among these counts throughout the matrix traversal, we obtain the answer.

Code Solutions

# Define the function to find the longest line of consecutive ones in matrix
def longestLine(mat):
    if not mat or not mat[0]:
        return 0

    rows, cols = len(mat), len(mat[0])
    # Initialize dp arrays for 4 directions: horizontal, vertical, diag, anti-diag
    horizontal = [[0] * cols for _ in range(rows)]
    vertical = [[0] * cols for _ in range(rows)]
    diagonal = [[0] * cols for _ in range(rows)]
    anti_diag = [[0] * cols for _ in range(rows)]

    longest = 0
    # Iterate over each cell
    for i in range(rows):
        for j in range(cols):
            if mat[i][j] == 1:
                # Horizontal: add one from left cell if exists
                horizontal[i][j] = (horizontal[i][j-1] if j > 0 else 0) + 1
                # Vertical: add one from top cell if exists
                vertical[i][j] = (vertical[i-1][j] if i > 0 else 0) + 1
                # Diagonal: add one from top-left cell if exists
                diagonal[i][j] = (diagonal[i-1][j-1] if i > 0 and j > 0 else 0) + 1
                # Anti-diagonal: add one from top-right cell if exists
                anti_diag[i][j] = (anti_diag[i-1][j+1] if i > 0 and j < cols - 1 else 0) + 1

                # Update the longest line found so far
                current_max = max(horizontal[i][j], vertical[i][j], diagonal[i][j], anti_diag[i][j])
                longest = max(longest, current_max)
    
    return longest

# Example usage:
matrix = [
    [0,1,1,0],
    [0,1,1,0],
    [0,0,0,1]
]
print(longestLine(matrix))  # Output should be 3
← Back to All Questions