Longest Line of Consecutive One in Matrix

medium array dp matrix

Problem

Return the longest line of consecutive 1's in a binary matrix in any of horizontal, vertical, diagonal, or anti-diagonal direction.

Inputmat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]

Output3

Per direction, dp[i][j] = mat[i][j] == 1 ? dp[prev] + 1 : 0.

matrix (rows ; ,)

def longest_line(mat):
    if not mat or not mat[0]: return 0
    R, C = len(mat), len(mat[0])
    dp = [[[0]*4 for _ in range(C)] for _ in range(R)]
    best = 0
    for i in range(R):
        for j in range(C):
            if mat[i][j] == 0: continue
            dp[i][j][0] = (dp[i][j-1][0] if j else 0) + 1
            dp[i][j][1] = (dp[i-1][j][1] if i else 0) + 1
            dp[i][j][2] = (dp[i-1][j-1][2] if i and j else 0) + 1
            dp[i][j][3] = (dp[i-1][j+1][3] if i and j + 1 < C else 0) + 1
            best = max(best, *dp[i][j])
    return best

function longestLine(mat) {
  const R = mat.length, C = mat[0].length;
  const dp = Array.from({ length: R }, () => Array.from({ length: C }, () => [0, 0, 0, 0]));
  let best = 0;
  for (let i = 0; i < R; i++) for (let j = 0; j < C; j++) {
    if (!mat[i][j]) continue;
    dp[i][j][0] = (j ? dp[i][j-1][0] : 0) + 1;
    dp[i][j][1] = (i ? dp[i-1][j][1] : 0) + 1;
    dp[i][j][2] = (i && j ? dp[i-1][j-1][2] : 0) + 1;
    dp[i][j][3] = (i && j + 1 < C ? dp[i-1][j+1][3] : 0) + 1;
    best = Math.max(best, ...dp[i][j]);
  }
  return best;
}

class Solution {
    public int longestLine(int[][] mat) {
        int R = mat.length, C = mat[0].length, best = 0;
        int[][][] dp = new int[R][C][4];
        for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
            if (mat[i][j] == 0) continue;
            dp[i][j][0] = (j > 0 ? dp[i][j-1][0] : 0) + 1;
            dp[i][j][1] = (i > 0 ? dp[i-1][j][1] : 0) + 1;
            dp[i][j][2] = (i > 0 && j > 0 ? dp[i-1][j-1][2] : 0) + 1;
            dp[i][j][3] = (i > 0 && j + 1 < C ? dp[i-1][j+1][3] : 0) + 1;
            for (int v : dp[i][j]) best = Math.max(best, v);
        }
        return best;
    }
}

int longestLine(vector>& mat) {
    int R = mat.size(), C = mat[0].size(), best = 0;
    vector>> dp(R, vector>(C, vector(4, 0)));
    for (int i = 0; i < R; i++) for (int j = 0; j < C; j++) {
        if (!mat[i][j]) continue;
        dp[i][j][0] = (j ? dp[i][j-1][0] : 0) + 1;
        dp[i][j][1] = (i ? dp[i-1][j][1] : 0) + 1;
        dp[i][j][2] = (i && j ? dp[i-1][j-1][2] : 0) + 1;
        dp[i][j][3] = (i && j + 1 < C ? dp[i-1][j+1][3] : 0) + 1;
        for (int v : dp[i][j]) best = max(best, v);
    }
    return best;
}

Explanation

A line of 1s can run in four directions: across a row, down a column, or along either diagonal. The neat trick is that the longest line ending at a cell in any direction is just one more than the line ending at the cell right behind it in that same direction.

So for every cell we keep four counters, stored as dp[i][j] with slots [H, V, diag↘, diag↗]. If the cell is a 1, each counter copies its neighbour behind it and adds 1; if the cell is a 0, all counters stay 0 because the line is broken.

The neighbour behind depends on direction: horizontal looks at dp[i][j-1], vertical at dp[i-1][j], the down-right diagonal at dp[i-1][j-1], and the up-right diagonal at dp[i-1][j+1]. We guard the edges so we never read outside the grid.

This works because consecutive 1s build up step by step. Each cell only needs the answer from the cell immediately before it, which we already computed, so a single pass fills everything in.

Example: in [[0,1,1,0],[0,1,1,0],[0,0,0,1]] the two stacked 1s in a column give a vertical run of 2, and the diagonal touching the bottom-right 1 reaches length 3, which becomes best.

Time: O(R·C) Space: O(R·C)