Longest Line of Consecutive One in Matrix

Longest Line of Consecutive One in Matrix

What is this problem about?

The Longest Line of Consecutive One in Matrix interview question provides you with a 2D binary matrix containing 0s and 1s. Your objective is to find the length of the longest contiguous line of 1s. This line can be formed in any of four directions: horizontally, vertically, diagonally (top-left to bottom-right), or anti-diagonally (top-right to bottom-left).

Why is this asked in interviews?

This is a comprehensive matrix traversal problem. Interviewers ask it because it requires careful state management across multiple dimensions. It tests a candidate's ability to extrapolate a simple 1D concept (counting consecutive ones) into a 2D grid involving diagonal logic. It's a great indicator of how well a candidate handles edge cases and avoids out-of-bounds matrix errors.

Algorithmic pattern used

This is solved using Dynamic Programming. We can use a 3D array dp[row][col][4] where the third dimension stores the longest line of 1s ending at (row, col) for each of the four directions.

• Direction 0 (Horizontal): dp[r][c][0] = dp[r][c-1][0] + 1
• Direction 1 (Vertical): dp[r][c][1] = dp[r-1][c][1] + 1
• Direction 2 (Diagonal): dp[r][c][2] = dp[r-1][c-1][2] + 1
• Direction 3 (Anti-diagonal): dp[r][c][3] = dp[r-1][c+1][3] + 1

Example explanation

Consider the matrix:

0 1 1 0
0 1 1 0
0 0 0 1

We process cell by cell. At (0, 1), it's a 1. Horizontal=1, Vertical=1, Diag=1, Anti=1. At (0, 2), it's a 1. Horizontal gets (0, 1)'s Horizontal + 1 = 2. At (1, 1), it's a 1. Vertical gets (0, 1)'s Vertical + 1 = 2. At (1, 2), it's a 1.

• Horizontal: (1, 1) is 1, so 1+1 = 2.
• Vertical: (0, 2) is 1, so 1+1 = 2.
• Diagonal: looks at (0, 1) which is 1. So 1+1 = 2. At (2, 3), it's a 1. Diagonal looks at (1, 2) which is 1. So 1+1 = 2. The maximum value across all cells and all directions is 2.

Common mistakes candidates make

Candidates frequently try to solve this using Depth-First Search (DFS) from every single 1. Since a DFS would need to go in 4 specific directions without bending, it essentially mimics the DP solution but with massive call stack overhead and repeated work, often resulting in Time Limit Exceeded. Another common error is messing up the anti-diagonal array bounds (col + 1), causing out-of-bounds exceptions.

Interview preparation tip

When preparing for matrix path-finding problems that restrict movement to straight lines, always default to bottom-up Dynamic Programming rather than DFS. Practice writing the 4 directional checks cleanly. Furthermore, challenge yourself to optimize the space complexity: since the current row only depends on the previous row, you can reduce the $O(M \times N \times 4)$ space down to $O(N \times 4)$ by only keeping track of the previous row.