Longest line of consecutive one in matrix

Array Dynamic Programming Matrix

50.6% acceptance

Mar 31, 2026

906

119

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn longest_line(mat: Vec<Vec<i32>>) -> i32 {
    let m = mat.len();
    let n = mat[0].len();
    let mut dp = vec![vec![[0i32; 4]; n]; m];
    let mut ans = 0;
    for i in 0..m {
      for j in 0..n {
        if mat[i][j] == 1 {
          dp[i][j][0] = if j > 0 { dp[i][j - 1][0] + 1 } else { 1 };
          dp[i][j][1] = if i > 0 { dp[i - 1][j][1] + 1 } else { 1 };
          dp[i][j][2] = if i > 0 && j > 0 { dp[i - 1][j - 1][2] + 1 } else { 1 };
          dp[i][j][3] = if i > 0 && j + 1 < n { dp[i - 1][j + 1][3] + 1 } else { 1 };
          ans = ans.max(dp[i][j][0]).max(dp[i][j][1]).max(dp[i][j][2]).max(dp[i][j][3]);
        }
      }
    }
    ans
  }
}