Is Longest Line of Consecutive One in Matrix easy or hard?

The problem is rated Medium on LeetCode. The challenge is recognizing that four directional sequences must be tracked simultaneously and that dynamic programming avoids repeated scanning of the same lines.

Longest Line of Consecutive One in Matrix Python/Java solution

The typical implementation uses a DP table where dp[i][j][k] represents the longest streak ending at cell (i, j) for one of four directions. Python, Java, C++, and Go implementations follow the same logic: update directional states based on neighboring cells and track the maximum length.

How to solve Longest Line of Consecutive One in Matrix in O(n)?

Process the matrix using dynamic programming. For every cell with value 1, compute four directional streaks using previously computed neighbors: left, up, up-left, and up-right. This ensures the entire grid is processed in O(m*n) time without repeatedly scanning lines.

What is the best approach for Longest Line of Consecutive One in Matrix?

Dynamic programming is the best approach. For each cell containing 1, maintain four counts representing horizontal, vertical, diagonal, and anti-diagonal lines ending at that cell. Each state extends from a neighboring cell's value, allowing the matrix to be processed in O(m*n) time.

Is Longest Line of Consecutive One in Matrix asked at Google/Amazon/Meta?

Matrix dynamic programming problems like this commonly appear in interviews at companies such as Amazon, Google, and Meta. Variants involving directional DP or longest sequences in grids are frequently used to test grid traversal and DP reasoning.

What data structure is used in Longest Line of Consecutive One in Matrix?

The solution primarily uses arrays and dynamic programming tables. A 3D DP array or four separate matrices track consecutive counts for horizontal, vertical, diagonal, and anti-diagonal directions.

What is the time complexity of Longest Line of Consecutive One in Matrix?

The optimal dynamic programming solution runs in O(m*n) time, where m is the number of rows and n is the number of columns. Each cell is processed once while updating four directional counts, resulting in constant work per cell.

Description Hints 4 Solution Video 18:04

562. Longest Line of Consecutive One in Matrix

Medium50.5% acceptance1 companyPremium elsewhere, free here

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 <= 10⁴
1 <= m * n <= 10⁴
mat[i][j] is either 0 or 1.

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

One solution is to count ones in each direction separately and find the longest line. Don't you think it will take too much lines of code?

Hint 2

Is it possible to use some extra space to make the solution simple?

Hint 3

Can we use dynamic programming to make use of intermediate results?

Hint 4

Think of a 3D array which can be used to store the longest line obtained so far for each direction.

18:04

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[0,1,1,0],[0,1,1,0],[0,0,0,1]]

Input

[[1,1,1,1],[0,1,1,0],[0,0,0,1]]

Your code is saved on this device.Solution