Longest Line of Consecutive One in Matrix - Solution & Explanation

Problem Overview: Given a binary matrix, find the maximum number of consecutive 1s that appear in a straight line. A valid line can be horizontal, vertical, diagonal, or anti-diagonal. The goal is to scan the grid and return the length of the longest such sequence.

Approach 1: Brute Force Directional Scan (O(m*n*max(m,n)) time, O(1) space)

The straightforward method checks every cell containing 1 and extends in four directions: right, down, diagonal, and anti-diagonal. For each direction, keep moving while the next cell remains 1. Track the length and update the global maximum. This approach is simple but inefficient because the same sequences are recomputed multiple times. In dense matrices, repeated directional scans significantly increase runtime.

Approach 2: Dynamic Programming with Direction States (O(m*n) time, O(m*n) space)

The efficient solution uses dynamic programming to track streak lengths ending at each cell. For every matrix[i][j] == 1, maintain four DP values: horizontal, vertical, diagonal, and anti-diagonal. Each value extends from a previously computed neighbor. Horizontal depends on (i, j-1), vertical on (i-1, j), diagonal on (i-1, j-1), and anti-diagonal on (i-1, j+1). Add 1 to the corresponding previous value and store it. This avoids re-scanning sequences and ensures each cell is processed once.

Implementation typically uses a 3D DP array dp[i][j][4] or four separate matrices. When the cell value is 0, all streak counts remain zero. When it's 1, compute the four directions using previously calculated states. Track the maximum value seen across all directions. The algorithm runs in O(m*n) time because each cell performs constant work.

An alternative optimization compresses memory by keeping only the previous row for vertical and diagonal transitions while computing the current row for horizontal and anti-diagonal values. This reduces space to O(n) while maintaining the same time complexity.

This problem is a classic application of array traversal combined with directional dynamic programming. The key insight is recognizing overlapping subproblems: the longest line ending at a cell depends on previously solved neighbors rather than scanning entire lines repeatedly.

Recommended for interviews: The dynamic programming approach is what interviewers expect. Brute force shows you understand the four valid directions, but the DP solution demonstrates optimization skills and the ability to reuse computed state. Explaining how each direction depends on a specific neighbor is usually the critical insight interviewers look for.