562. Longest Line of Consecutive One in Matrix
Problem Description
The problem presents a binary matrix (mat
), which is simply a grid made up of 0s and 1s. Our goal is to find the maximal length of a continuous line of 1s that could be arranged in any of four possible directions: horizontal, vertical, diagonal from top left to bottom right (referred to as 'diagonal'), and diagonal from top right to bottom left (referred to as 'anti-diagonal'). The task is to return the length of this longest line.
Intuition
To solve this problem, we can execute a comprehensive scan of the matrix. This involves checking each direction for each element in the matrix that is a 1 and updating counts of consecutive 1s in each direction.
The intuition for the solution can be broken down as follows:
-
For each cell that contains a 1 in the matrix, we have the potential to extend a line horizontally, vertically, diagonally, or anti-diagonally.
-
We can maintain four separate 2D arrays (of the same dimensions as the original matrix, with an extra buffer row and column to handle edge cases) to keep track of the maximum line length in each of the four directions at each cell.
a[][]
for the vertical directionb[][]
for the horizontal directionc[][]
for the diagonal directiond[][]
for the anti-diagonal direction
-
By iterating over each cell in the matrix, we update the arrays for directions only if the current cell is a 1. For example, the length of the vertical line at
a[i][j]
is 1 plus the length ata[i - 1][j]
if the cell atmat[i - 1][j - 1]
is a 1. -
Because we are only interested in consecutive 1s, whenever we hit a 0, the count resets to 0.
-
At every step, we update a variable
ans
to store the maximum line length found so far, resulting in having the maximum length by the time we end our scan. -
The use of padding (an extra row and column) in arrays a, b, c, and d allows easy indexing without the need to check the matrix boundaries, which simplifies the logic and makes the code cleaner.
Following this approach allows us to resolve the problem with time complexity that is linear with respect to the number of cells in the matrix (O(m * n)) and with extra space for the four tracking matrices.
Learn more about Dynamic Programming patterns.
Solution Approach
The solution approach for this problem involves dynamic programming to keep track of the longest line of 1s for each of the four directions (horizontal, vertical, diagonal, and anti-diagonal) at every cell. Here is a breakdown of how the implementation works, tying back to the Python code provided:
-
Initialization: The solution first initializes four 2D arrays,
a
,b
,c
, andd
, each withm + 2
rows andn + 2
columns. These arrays are used to store the maximum length of consecutive ones up to that point in the matrix for each direction. The extra rows and columns serve as a buffer that simplifies boundary condition handling. -
Iterative Processing: The algorithm iterates through each cell in the matrix using two nested loops. The outer loop goes down each row, and the inner loop goes across each column. Only cells with a value of 1 are processed to extend the lines.
-
Updating Directional Counts: For each cell with a 1, the four arrays are updated as follows:
a[i][j]
is updated toa[i - 1][j] + 1
, incrementing the count of vertical consecutive ones from the top.b[i][j]
is updated tob[i][j - 1] + 1
, incrementing the count of horizontal consecutive ones from the left.c[i][j]
is updated toc[i - 1][j - 1] + 1
, incrementing the count of diagonal consecutive ones from the top left.d[i][j]
is updated tod[i - 1][j + 1] + 1
, incrementing the count of anti-diagonal consecutive ones from the top right.
-
Updating the Answer: The maximum value of the four array cells at the current position (
a[i][j]
,b[i][j]
,c[i][j]
,d[i][j]
) is compared with the current answer (ans
). If any of them is greater,ans
is updated. This ensuresans
always holds the maximum line length found up to that point. -
Return the Result: After completely scanning the matrix, the maximum length (
ans
) is returned as the answer.
The data structures used, in this case, are additional 2D arrays that help us track the solution state as we go, characteristic of dynamic programming. The implementation is relatively straightforward and relies on previous states to compute the current state. This ensures that at any given point in the matrix, we know the longest line of 1s that could be formed in any of the four directions without having to re-scan any part of the matrix, which is efficient and reduces the overall time complexity of the algorithm.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small binary matrix example:
1mat = [ 2 [0, 1, 1, 0], 3 [0, 1, 1, 1], 4 [1, 0, 0, 1] 5]
Following the steps outlined in the solution approach:
-
Initialization: We create four extra 2D arrays
a
,b
,c
, andd
, each with dimensions4 x 5
to accommodate the buffer rows and columns. -
Iterative Processing: We step through each cell in the matrix one by one.
-
Updating Directional Counts and Answer: We update the counts in our four arrays only at positions where the corresponding cell in
mat
is1
. Assumeans = 0
at the start.
To better understand, let's look at the updates after processing the first two rows:
After the first row:
1a (vertical) b (horizontal) c (diagonal) d (anti-diagonal) 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 1 2 0 0 0 0 1 2 0 0 0 0 1 0 0 1 2 0 40 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5ans = 2
Here, ans
is 2, as that is the largest count in any of the arrays.
After the second row:
1a (vertical) b (horizontal) c (diagonal) d (anti-diagonal) 20 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 30 0 1 2 0 0 0 0 1 2 0 0 0 0 1 0 0 1 2 0 40 0 2 3 0 0 0 0 1 2 3 0 0 0 1 2 0 0 0 3 1 5ans = 3
After processing the cell mat[1][3]
, ans
updates to 3, as that is now the highest value found.
- Return the Result: After completely iterating over the matrix, we find that the
ans
is3
, which indicates the length of the longest continuous line of 1s. We would return3
in this case.
And so, by iterating over the matrix and updating our directional counts, we can determine that the longest continuous line of 1
s in mat
spans 3 cells and is found horizontally in the second row.
Solution Implementation
1from typing import List # Import typing to use List type hint
2
3class Solution:
4 def longestLine(self, matrix: List[List[int]]) -> int:
5 # Get the dimensions of the matrix
6 rows, cols = len(matrix), len(matrix[0])
7
8 # Initialize four matrices to keep track of continuous 1s in all four directions:
9 # horizontal, vertical, diagonal, anti-diagonal
10 horizontal = [[0] * (cols + 2) for _ in range(rows + 2)]
11 vertical = [[0] * (cols + 2) for _ in range(rows + 2)]
12 diagonal = [[0] * (cols + 2) for _ in range(rows + 2)]
13 anti_diagonal = [[0] * (cols + 2) for _ in range(rows + 2)]
14
15 # Variable to store the maximum length of continuous 1s
16 max_length = 0
17
18 # Iterate through the matrix
19 for i in range(1, rows + 1):
20 for j in range(1, cols + 1):
21 # Value of the current cell in the input matrix
22 value = matrix[i - 1][j - 1]
23 if value == 1:
24 # Update counts for all four directions by adding 1 to the counts from previous
25 # relevant cells (up, left, top-left diagonal, top-right diagonal).
26 horizontal[i][j] = horizontal[i][j - 1] + 1
27 vertical[i][j] = vertical[i - 1][j] + 1
28 diagonal[i][j] = diagonal[i - 1][j - 1] + 1
29 anti_diagonal[i][j] = anti_diagonal[i - 1][j + 1] + 1
30
31 # Update the max_length for the current cell's longest line of continuous 1s.
32 max_length = max(max_length, horizontal[i][j], vertical[i][j],
33 diagonal[i][j], anti_diagonal[i][j])
34
35 # Return the maximum length of continuous 1s found.
36 return max_length
37
1class Solution {
2 public int longestLine(int[][] mat) {
3 // Get the number of rows and columns in the matrix
4 int rows = mat.length, cols = mat[0].length;
5 int[][] horizontal = new int[rows + 2][cols + 2];
6 int[][] vertical = new int[rows + 2][cols + 2];
7 int[][] diagonal = new int[rows + 2][cols + 2];
8 int[][] antiDiagonal = new int[rows + 2][cols + 2];
9
10 // Initialize a variable to keep track of the maximum length
11 int maxLength = 0;
12
13 // Iterate over each cell in the matrix
14 for (int i = 1; i <= rows; ++i) {
15 for (int j = 1; j <= cols; ++j) {
16 // If the current cell has a value of 1
17 if (mat[i - 1][j - 1] == 1) {
18 // Update the counts for each direction (horizontal, vertical, diagonal, antiDiagonal)
19 horizontal[i][j] = horizontal[i][j - 1] + 1; // Left
20 vertical[i][j] = vertical[i - 1][j] + 1; // Up
21 diagonal[i][j] = diagonal[i - 1][j - 1] + 1; // Top-left
22 antiDiagonal[i][j] = antiDiagonal[i - 1][j + 1] + 1; // Top-right
23
24 // Update the maximum length if a higher count is found
25 maxLength = getMax(maxLength, horizontal[i][j], vertical[i][j], diagonal[i][j], antiDiagonal[i][j]);
26 }
27 }
28 }
29 // Return the maximum length of a line of consecutive ones
30 return maxLength;
31 }
32
33 // Helper function to calculate the maximum value
34 private int getMax(int... values) {
35 int max = 0;
36 for (int value : values) {
37 max = Math.max(max, value);
38 }
39 return max;
40 }
41}
42
1#include <vector>
2#include <algorithm> // For max()
3using namespace std;
4
5class Solution {
6public:
7 int longestLine(vector<vector<int>>& matrix) {
8 int rows = matrix.size(), cols = matrix[0].size();
9
10 // Create 2D vectors with extra padding to handle indices during DP calculations
11 vector<vector<int>> vertical(rows + 2, vector<int>(cols + 2, 0));
12 vector<vector<int>> horizontal(rows + 2, vector<int>(cols + 2, 0));
13 vector<vector<int>> diagonal(rows + 2, vector<int>(cols + 2, 0));
14 vector<vector<int>> antiDiagonal(rows + 2, vector<int>(cols + 2, 0));
15
16 int maxLength = 0; // To keep track of the longest line of consecutive ones
17
18 // Iterate through each cell of the matrix to fill DP tables
19 for (int i = 1; i <= rows; ++i) {
20 for (int j = 1; j <= cols; ++j) {
21 // Only process the cell if it contains a '1'
22 if (matrix[i - 1][j - 1] == 1) {
23 // Update the dynamic programming tables
24 // Compute number of consecutive ones in all directions
25 vertical[i][j] = vertical[i - 1][j] + 1; // Count consecutive ones vertically
26 horizontal[i][j] = horizontal[i][j - 1] + 1; // Count consecutive ones horizontally
27 diagonal[i][j] = diagonal[i - 1][j - 1] + 1; // Count consecutive ones diagonally
28 antiDiagonal[i][j] = antiDiagonal[i - 1][j + 1] + 1; // Count consecutive ones anti-diagonally
29
30 // Check if the current count is larger than the current maximum length
31 int currentMax = max(vertical[i][j], max(horizontal[i][j],
32 max(diagonal[i][j], antiDiagonal[i][j])));
33 maxLength = max(maxLength, currentMax);
34 }
35 }
36 }
37
38 // Return the length of the longest consecutive line of ones found
39 return maxLength;
40 }
41};
42
1function longestLine(matrix: number[][]): number {
2 let rows = matrix.length;
3 let cols = matrix[0].length;
4
5 // Initialize 2D arrays with extra padding to handle indices during dynamic programming calculations
6 let vertical = Array.from({ length: rows + 2 }, () => Array(cols + 2).fill(0));
7 let horizontal = Array.from({ length: rows + 2 }, () => Array(cols + 2).fill(0));
8 let diagonal = Array.from({ length: rows + 2 }, () => Array(cols + 2).fill(0));
9 let antiDiagonal = Array.from({ length: rows + 2 }, () => Array(cols + 2).fill(0));
10
11 let maxLength = 0; // To keep track of the longest line of consecutive ones
12
13 // Iterate through each cell of the matrix to fill the DP arrays
14 for (let i = 1; i <= rows; i++) {
15 for (let j = 1; j <= cols; j++) {
16 // Only process the cell if it contains a '1'
17 if (matrix[i - 1][j - 1] === 1) {
18 // Update the dynamic programming arrays
19 // Compute the number of consecutive ones in all directions
20 vertical[i][j] = vertical[i - 1][j] + 1; // Count consecutive ones vertically
21 horizontal[i][j] = horizontal[i][j - 1] + 1; // Count consecutive ones horizontally
22 diagonal[i][j] = diagonal[i - 1][j - 1] + 1; // Count consecutive ones diagonally
23 antiDiagonal[i][j] = antiDiagonal[i - 1][j + 1] + 1; // Count consecutive ones anti-diagonally
24
25 // Check if the current count is larger than the maximum length found so far
26 let currentMax = Math.max(vertical[i][j], Math.max(horizontal[i][j],
27 Math.max(diagonal[i][j], antiDiagonal[i][j])));
28 maxLength = Math.max(maxLength, currentMax);
29 }
30 }
31 }
32
33 // Return the length of the longest consecutive line of ones found
34 return maxLength;
35}
36
Time and Space Complexity
The time complexity of the provided code is O(m * n)
, where m
is the number of rows and n
is the number of columns in the input matrix mat
. This complexity arises because the code iterates over each cell of the matrix exactly once, performing a constant number of operations for each cell.
The space complexity of the code is also O(m * n)
because it creates four auxiliary matrices (a
, b
, c
, d
), each of the same size as the input matrix mat
. These matrices are used to keep track of the length of consecutive ones in four directions - horizontal, vertical, diagonal, and anti-diagonal.
Learn more about how to find time and space complexity quickly using problem constraints.
What data structure does Breadth-first search typically uses to store intermediate states?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.