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 Alex Chen, 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

Practice these live with InterviewChamp.AI

Drill Longest Line of Consecutive One in Matrix and 2D Dynamic Programming problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →