Skip to main content

562. Longest Line of Consecutive One in Matrix

medium

Find the longest consecutive run of 1s in a binary matrix along any of four directions: horizontal, vertical, diagonal, or anti-diagonal. Per-cell 4-channel DP — each channel inherits from its directional predecessor.

By Sam K., Founder, InterviewChamp.AI · Last verified

Problem

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.

Constraints

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

Examples

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

For each cell, keep four DP values: longest consecutive 1s ending here in each of horizontal, vertical, diagonal, anti-diagonal directions.

Hint 2

Each channel inherits from one specific predecessor: horizontal inherits from (i, j-1), vertical from (i-1, j), diagonal from (i-1, j-1), anti-diagonal from (i-1, j+1).

Hint 3

If mat[i][j] == 0 set all four to 0. If 1, each channel = predecessor + 1.

Hint 4

Track the global max across all four channels.

Solution approach

Reveal approach

Bottom-up DP with a 4-channel state per cell. dp[i][j] is a length-4 tuple holding the longest run of 1s ending at (i, j) for each direction: horizontal (left to right), vertical (top to bottom), diagonal (top-left to bottom-right), anti-diagonal (top-right to bottom-left). For each cell in row-major order, if mat[i][j] == 0, set all four to 0. Otherwise: horizontal = (j > 0 ? dp[i][j-1].h : 0) + 1, vertical = (i > 0 ? dp[i-1][j].v : 0) + 1, diagonal = (i > 0 && j > 0 ? dp[i-1][j-1].d : 0) + 1, anti = (i > 0 && j < n-1 ? dp[i-1][j+1].a : 0) + 1. Update the global max. Anti-diagonal looks at the previous row, j+1, which is fine in row-major order because the previous row is fully filled before the current row starts.

Complexity

Time
O(m * n)
Space
O(m * n)

Related patterns

  • dynamic-programming
  • grid-dp

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Google

More 2D Dynamic Programming practice problems

See all 2D Dynamic Programming problems →