Welcome to Subscribe On Youtube

562. Longest Line of Consecutive One in Matrix

Description

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.

 

Example 1:

Input: mat = [[0,1,1,0],[0,1,1,0],[0,0,0,1]]
Output: 3

Example 2:

Input: mat = [[1,1,1,1],[0,1,1,0],[0,0,0,1]]
Output: 4

 

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.

Solutions

• Java
• C++
• Python
• Go

• class Solution {
      public int longestLine(int[][] mat) {
          int m = mat.length, n = mat[0].length;
          int[][] a = new int[m + 2][n + 2];
          int[][] b = new int[m + 2][n + 2];
          int[][] c = new int[m + 2][n + 2];
          int[][] d = new int[m + 2][n + 2];
          int ans = 0;
          for (int i = 1; i <= m; ++i) {
              for (int j = 1; j <= n; ++j) {
                  if (mat[i - 1][j - 1] == 1) {
                      a[i][j] = a[i - 1][j] + 1;
                      b[i][j] = b[i][j - 1] + 1;
                      c[i][j] = c[i - 1][j - 1] + 1;
                      d[i][j] = d[i - 1][j + 1] + 1;
                      ans = max(ans, a[i][j], b[i][j], c[i][j], d[i][j]);
                  }
              }
          }
          return ans;
      }
  
      private int max(int... arr) {
          int ans = 0;
          for (int v : arr) {
              ans = Math.max(ans, v);
          }
          return ans;
      }
  }
  

• class Solution {
  public:
      int longestLine(vector<vector<int>>& mat) {
          int m = mat.size(), n = mat[0].size();
          vector<vector<int>> a(m + 2, vector<int>(n + 2));
          vector<vector<int>> b(m + 2, vector<int>(n + 2));
          vector<vector<int>> c(m + 2, vector<int>(n + 2));
          vector<vector<int>> d(m + 2, vector<int>(n + 2));
          int ans = 0;
          for (int i = 1; i <= m; ++i) {
              for (int j = 1; j <= n; ++j) {
                  if (mat[i - 1][j - 1]) {
                      a[i][j] = a[i - 1][j] + 1;
                      b[i][j] = b[i][j - 1] + 1;
                      c[i][j] = c[i - 1][j - 1] + 1;
                      d[i][j] = d[i - 1][j + 1] + 1;
                      ans = max(ans, max(a[i][j], max(b[i][j], max(c[i][j], d[i][j]))));
                  }
              }
          }
          return ans;
      }
  };
  

• class Solution:
      def longestLine(self, mat: List[List[int]]) -> int:
          m, n = len(mat), len(mat[0])
          a = [[0] * (n + 2) for _ in range(m + 2)]
          b = [[0] * (n + 2) for _ in range(m + 2)]
          c = [[0] * (n + 2) for _ in range(m + 2)]
          d = [[0] * (n + 2) for _ in range(m + 2)]
          ans = 0
          for i in range(1, m + 1):
              for j in range(1, n + 1):
                  v = mat[i - 1][j - 1]
                  if v:
                      a[i][j] = a[i - 1][j] + 1
                      b[i][j] = b[i][j - 1] + 1
                      c[i][j] = c[i - 1][j - 1] + 1
                      d[i][j] = d[i - 1][j + 1] + 1
                      ans = max(ans, a[i][j], b[i][j], c[i][j], d[i][j])
          return ans
  
  

• func longestLine(mat [][]int) (ans int) {
  	m, n := len(mat), len(mat[0])
  	f := make([][][4]int, m+2)
  	for i := range f {
  		f[i] = make([][4]int, n+2)
  	}
  	for i := 1; i <= m; i++ {
  		for j := 1; j <= n; j++ {
  			if mat[i-1][j-1] == 1 {
  				f[i][j][0] = f[i-1][j][0] + 1
  				f[i][j][1] = f[i][j-1][1] + 1
  				f[i][j][2] = f[i-1][j-1][2] + 1
  				f[i][j][3] = f[i-1][j+1][3] + 1
  				for _, v := range f[i][j] {
  					if ans < v {
  						ans = v
  					}
  				}
  			}
  		}
  	}
  	return
  }
  

All Problems

All Solutions