Jobs

Interviews

Discussions

Longest Line of Consecutive One in Matrix

Medium

Asked by:

23 views

Topics:

ArraysDynamic Programming

Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.

The line could be horizontal, vertical, diagonal, or anti-diagonal.

Example 1:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

Example 2:

Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 200
mat[i][j] is 0 or 1.

Try coding it in LeetCode

Longest Line of Consecutive One in Matrix

Medium

Asked by:

23 views

Topics:

ArraysDynamic Programming

Given an m x n binary matrix mat, return the length of the longest line of consecutive one in the matrix.

The line could be horizontal, vertical, diagonal, or anti-diagonal.

Example 1:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

Example 2:

Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4

Constraints:

m == mat.length
n == mat[i].length
1 <= m, n <= 200
mat[i][j] is 0 or 1.

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and are there any limits on the number of rows and columns?
What is the data type of the matrix elements? Can I assume they are integers, and specifically, can they only be 0 or 1?
If the matrix is empty or contains no '1's, what should I return? Should I return 0, or is there another specified value?
By 'line', do you mean horizontal, vertical, or diagonal (both positive and negative slope)? Or all of them?
If there are multiple lines with the same maximum length of consecutive ones, should I return the length of any one of them, or is there a specific line I should prioritize finding?

Brute Force Solution

Approach

We are given a grid of zeros and ones, and we want to find the longest line of consecutive ones. The brute force way is to check every possible line, in every possible direction, to see how many consecutive ones there are.

Here's how the algorithm would work step-by-step:

Look at each cell in the grid, one by one.
From each cell, imagine drawing a line going to the right. Count how many consecutive ones you see in that direction.
From the same cell, imagine drawing a line going downwards. Count how many consecutive ones you see in that direction.
From that same cell, also try drawing a line diagonally downwards to the right and count the consecutive ones.
Finally, from the same cell, imagine drawing a line diagonally downwards to the left and count the consecutive ones.
Repeat steps 2-5 for every single cell in the grid.
Keep track of the longest line of consecutive ones that you've found so far.
After checking every cell and every direction, report the longest line you found.

Code Implementation

def longest_line_of_consecutive_one_brute_force(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    max_length = 0

    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] == 1:

                # Check right
                current_length = 0
                for k in range(col_index, cols):
                    if matrix[row_index][k] == 1:
                        current_length += 1
                    else:
                        break
                max_length = max(max_length, current_length)

                # Check down
                current_length = 0
                for k in range(row_index, rows):
                    if matrix[k][col_index] == 1:
                        current_length += 1
                    else:
                        break
                max_length = max(max_length, current_length)

                # Check diagonal down-right
                current_length = 0
                k = 0
                while row_index + k < rows and col_index + k < cols:
                    if matrix[row_index + k][col_index + k] == 1:
                        current_length += 1
                        k += 1
                    else:
                        break
                max_length = max(max_length, current_length)

                # Check diagonal down-left
                current_length = 0

                # Need to check the diagonal to the left
                k = 0
                while row_index + k < rows and col_index - k >= 0:
                    if matrix[row_index + k][col_index - k] == 1:
                        current_length += 1
                        k += 1
                    else:
                        break
                max_length = max(max_length, current_length)

    return max_length

Big(O) Analysis

Time Complexity

O(m * n * k) – We iterate through each cell in the m x n grid, resulting in m * n operations. For each cell, we check four directions: right, down, diagonal down-right, and diagonal down-left. In the worst-case scenario, for each of these directions, we might traverse the entire length of the longest possible line, which is limited by the maximum of the number of rows and columns which we denote as k. Therefore, for each cell, we perform at most k operations and, the overall time complexity is O(m * n * k).

Space Complexity

O(1) – The provided brute force algorithm iterates through the matrix and calculates the longest line of consecutive ones by checking in four directions from each cell. It only needs to store a variable to keep track of the maximum length found so far. No additional data structures, such as arrays, hash maps, or recursion stacks are created that scale with the input size, which is the size of the matrix. Therefore, the space complexity is constant.

Optimal Solution

Approach

The most efficient way to find the longest line of ones is to use a technique similar to dynamic programming, building up results from smaller subproblems. Instead of recalculating lengths for each possible line direction, we store and reuse previous calculations. This allows us to efficiently determine the longest line in horizontal, vertical, and diagonal directions.

Here's how the algorithm would work step-by-step:

Imagine each spot in the matrix can store the length of the longest line of ones ending at that spot, in each of the four directions: horizontal, vertical, diagonal, and anti-diagonal.
Go through the matrix, spot by spot.
If you find a zero, the length of any line ending at that spot is zero in all directions. No need to do anything.
If you find a one, look at the spot immediately to the left to find the length of the longest horizontal line ending at that left spot. Add one to that length to find the length of the horizontal line ending at the current spot. Store this new length.
Do something similar for the vertical direction: Look at the spot immediately above. Add one to its longest vertical line length and store that at the current spot.
Also, do the same for the diagonal direction (look at the spot diagonally up and to the left) and the anti-diagonal direction (look at the spot diagonally up and to the right).
While going through the matrix, keep track of the overall longest line found so far. Update it whenever you find a longer line ending at the current spot in any direction.
After going through the entire matrix, the overall longest line you tracked is the answer.

Code Implementation

def longest_line(matrix):
    if not matrix:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    longest_streak = 0

    # Create DP tables for each direction
    horizontal_lines = [[0] * cols for _ in range(rows)]
    vertical_lines = [[0] * cols for _ in range(rows)]
    diagonal_lines = [[0] * cols for _ in range(rows)]
    anti_diagonal_lines = [[0] * cols for _ in range(rows)]

    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] == 1:
                # Update horizontal line length
                if col_index > 0:
                    horizontal_lines[row_index][col_index] = horizontal_lines[row_index][col_index - 1] + 1
                else:
                    horizontal_lines[row_index][col_index] = 1

                # Update vertical line length
                if row_index > 0:
                    vertical_lines[row_index][col_index] = vertical_lines[row_index - 1][col_index] + 1
                else:
                    vertical_lines[row_index][col_index] = 1

                # Diagonal line calculation
                if row_index > 0 and col_index > 0:
                    diagonal_lines[row_index][col_index] = diagonal_lines[row_index - 1][col_index - 1] + 1
                else:
                    diagonal_lines[row_index][col_index] = 1

                # Anti-diagonal line calculation
                if row_index > 0 and col_index < cols - 1:
                    anti_diagonal_lines[row_index][col_index] = anti_diagonal_lines[row_index - 1][col_index + 1] + 1
                else:
                    anti_diagonal_lines[row_index][col_index] = 1

                longest_streak = max(longest_streak,
                                     horizontal_lines[row_index][col_index],
                                     vertical_lines[row_index][col_index],
                                     diagonal_lines[row_index][col_index],
                                     anti_diagonal_lines[row_index][col_index])

    # The accumulated maximum length is the final result
    return longest_streak

Big(O) Analysis

Time Complexity

O(m * n) – The algorithm iterates through each cell of the input matrix once, where m is the number of rows and n is the number of columns. For each cell, it performs a constant number of operations (checking neighboring cells in four directions and updating the maximum length). Therefore, the time complexity is proportional to the number of cells in the matrix, resulting in O(m * n). If m is equal to n, this simplifies to O(n²).

Space Complexity

O(N) – The algorithm uses a dynamic programming approach where each spot in the matrix stores the length of the longest line of ones ending at that spot in four directions. This implies creating four matrices of the same dimensions as the input matrix to store these intermediate lengths. Therefore, the auxiliary space required is proportional to the size of the input matrix, where N is the number of elements in the input matrix (rows * columns). This results in O(N) space complexity.

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately as there are no elements to form a line.
Matrix with zero rows or zero columns	Return 0 immediately as there are no elements to form a line.
Matrix with only one row and/or one column	Iterate through the row/column and count consecutive 1s, returning the maximum count.
Matrix filled with all 0s	The algorithm should correctly return 0 as there are no consecutive 1s.
Matrix filled with all 1s	The result should be the maximum of rows/columns, or the length of the diagonal, as all are consecutive.
Large matrix (potential memory issues with dynamic programming solutions)	Optimize the solution to use constant space or consider streaming/iterative approaches to avoid storing the entire matrix state.
Integer overflow when counting long consecutive sequences	Use a data type that can accommodate the maximum possible length of a consecutive sequence (e.g., long).
Matrix with extremely skewed distribution of 1s, favoring one direction	The algorithm needs to efficiently handle cases where the longest line is only in one of the four directions without unnecessary computations.

Null or empty matrix

How to Handle:

Return 0 immediately as there are no elements to form a line.

Matrix with zero rows or zero columns

How to Handle:

Return 0 immediately as there are no elements to form a line.

Matrix with only one row and/or one column

How to Handle:

Iterate through the row/column and count consecutive 1s, returning the maximum count.

Matrix filled with all 0s

How to Handle:

The algorithm should correctly return 0 as there are no consecutive 1s.

Matrix filled with all 1s

How to Handle:

The result should be the maximum of rows/columns, or the length of the diagonal, as all are consecutive.

Large matrix (potential memory issues with dynamic programming solutions)

How to Handle:

Optimize the solution to use constant space or consider streaming/iterative approaches to avoid storing the entire matrix state.

Integer overflow when counting long consecutive sequences

How to Handle:

Use a data type that can accommodate the maximum possible length of a consecutive sequence (e.g., long).

Matrix with extremely skewed distribution of 1s, favoring one direction

How to Handle:

The algorithm needs to efficiently handle cases where the longest line is only in one of the four directions without unnecessary computations.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What are the dimensions of the matrix, and are there any limits on the number of rows and columns?
What is the data type of the matrix elements? Can I assume they are integers, and specifically, can they only be 0 or 1?
If the matrix is empty or contains no '1's, what should I return? Should I return 0, or is there another specified value?
By 'line', do you mean horizontal, vertical, or diagonal (both positive and negative slope)? Or all of them?
If there are multiple lines with the same maximum length of consecutive ones, should I return the length of any one of them, or is there a specific line I should prioritize finding?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Look at each cell in the grid, one by one.
From each cell, imagine drawing a line going to the right. Count how many consecutive ones you see in that direction.
From the same cell, imagine drawing a line going downwards. Count how many consecutive ones you see in that direction.
From that same cell, also try drawing a line diagonally downwards to the right and count the consecutive ones.
Finally, from the same cell, imagine drawing a line diagonally downwards to the left and count the consecutive ones.
Repeat steps 2-5 for every single cell in the grid.
Keep track of the longest line of consecutive ones that you've found so far.
After checking every cell and every direction, report the longest line you found.

Code Implementation

def longest_line_of_consecutive_one_brute_force(matrix):
    rows = len(matrix)
    cols = len(matrix[0]) if rows > 0 else 0
    max_length = 0

    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] == 1:

                # Check right
                current_length = 0
                for k in range(col_index, cols):
                    if matrix[row_index][k] == 1:
                        current_length += 1
                    else:
                        break
                max_length = max(max_length, current_length)

                # Check down
                current_length = 0
                for k in range(row_index, rows):
                    if matrix[k][col_index] == 1:
                        current_length += 1
                    else:
                        break
                max_length = max(max_length, current_length)

                # Check diagonal down-right
                current_length = 0
                k = 0
                while row_index + k < rows and col_index + k < cols:
                    if matrix[row_index + k][col_index + k] == 1:
                        current_length += 1
                        k += 1
                    else:
                        break
                max_length = max(max_length, current_length)

                # Check diagonal down-left
                current_length = 0

                # Need to check the diagonal to the left
                k = 0
                while row_index + k < rows and col_index - k >= 0:
                    if matrix[row_index + k][col_index - k] == 1:
                        current_length += 1
                        k += 1
                    else:
                        break
                max_length = max(max_length, current_length)

    return max_length

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine each spot in the matrix can store the length of the longest line of ones ending at that spot, in each of the four directions: horizontal, vertical, diagonal, and anti-diagonal.
Go through the matrix, spot by spot.
If you find a zero, the length of any line ending at that spot is zero in all directions. No need to do anything.
If you find a one, look at the spot immediately to the left to find the length of the longest horizontal line ending at that left spot. Add one to that length to find the length of the horizontal line ending at the current spot. Store this new length.
Do something similar for the vertical direction: Look at the spot immediately above. Add one to its longest vertical line length and store that at the current spot.
Also, do the same for the diagonal direction (look at the spot diagonally up and to the left) and the anti-diagonal direction (look at the spot diagonally up and to the right).
While going through the matrix, keep track of the overall longest line found so far. Update it whenever you find a longer line ending at the current spot in any direction.
After going through the entire matrix, the overall longest line you tracked is the answer.

Code Implementation

def longest_line(matrix):
    if not matrix:
        return 0

    rows = len(matrix)
    cols = len(matrix[0])
    longest_streak = 0

    # Create DP tables for each direction
    horizontal_lines = [[0] * cols for _ in range(rows)]
    vertical_lines = [[0] * cols for _ in range(rows)]
    diagonal_lines = [[0] * cols for _ in range(rows)]
    anti_diagonal_lines = [[0] * cols for _ in range(rows)]

    for row_index in range(rows):
        for col_index in range(cols):
            if matrix[row_index][col_index] == 1:
                # Update horizontal line length
                if col_index > 0:
                    horizontal_lines[row_index][col_index] = horizontal_lines[row_index][col_index - 1] + 1
                else:
                    horizontal_lines[row_index][col_index] = 1

                # Update vertical line length
                if row_index > 0:
                    vertical_lines[row_index][col_index] = vertical_lines[row_index - 1][col_index] + 1
                else:
                    vertical_lines[row_index][col_index] = 1

                # Diagonal line calculation
                if row_index > 0 and col_index > 0:
                    diagonal_lines[row_index][col_index] = diagonal_lines[row_index - 1][col_index - 1] + 1
                else:
                    diagonal_lines[row_index][col_index] = 1

                # Anti-diagonal line calculation
                if row_index > 0 and col_index < cols - 1:
                    anti_diagonal_lines[row_index][col_index] = anti_diagonal_lines[row_index - 1][col_index + 1] + 1
                else:
                    anti_diagonal_lines[row_index][col_index] = 1

                longest_streak = max(longest_streak,
                                     horizontal_lines[row_index][col_index],
                                     vertical_lines[row_index][col_index],
                                     diagonal_lines[row_index][col_index],
                                     anti_diagonal_lines[row_index][col_index])

    # The accumulated maximum length is the final result
    return longest_streak

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Null or empty matrix	Return 0 immediately as there are no elements to form a line.
Matrix with zero rows or zero columns	Return 0 immediately as there are no elements to form a line.
Matrix with only one row and/or one column	Iterate through the row/column and count consecutive 1s, returning the maximum count.
Matrix filled with all 0s	The algorithm should correctly return 0 as there are no consecutive 1s.
Matrix filled with all 1s	The result should be the maximum of rows/columns, or the length of the diagonal, as all are consecutive.
Large matrix (potential memory issues with dynamic programming solutions)	Optimize the solution to use constant space or consider streaming/iterative approaches to avoid storing the entire matrix state.
Integer overflow when counting long consecutive sequences	Use a data type that can accommodate the maximum possible length of a consecutive sequence (e.g., long).
Matrix with extremely skewed distribution of 1s, favoring one direction	The algorithm needs to efficiently handle cases where the longest line is only in one of the four directions without unnecessary computations.

Null or empty matrix

How to Handle:

Return 0 immediately as there are no elements to form a line.

Matrix with zero rows or zero columns

How to Handle:

Return 0 immediately as there are no elements to form a line.

Matrix with only one row and/or one column

How to Handle:

Iterate through the row/column and count consecutive 1s, returning the maximum count.

Matrix filled with all 0s

How to Handle:

The algorithm should correctly return 0 as there are no consecutive 1s.

Matrix filled with all 1s

How to Handle:

The result should be the maximum of rows/columns, or the length of the diagonal, as all are consecutive.

Large matrix (potential memory issues with dynamic programming solutions)

How to Handle:

Optimize the solution to use constant space or consider streaming/iterative approaches to avoid storing the entire matrix state.

Integer overflow when counting long consecutive sequences

How to Handle:

Use a data type that can accommodate the maximum possible length of a consecutive sequence (e.g., long).

Matrix with extremely skewed distribution of 1s, favoring one direction

How to Handle:

The algorithm needs to efficiently handle cases where the longest line is only in one of the four directions without unnecessary computations.