Longest Lit Line

Medium

A light board is a rectangular grid of bulbs panel: 1 means the bulb is on, 0 means it is off. Find the longest straight line of lit bulbs that follow one another with no gaps. The line may be horizontal, vertical, or run along either of the two diagonal directions. Return its length, the number of bulbs in it. If no bulb is lit, return 0.

Example 1

panel=[[1, 0, 1], [0, 1, 1], [1, 0, 1]] → 3

The right column is fully lit, three bulbs in a vertical line. The diagonal from the top-left corner breaks on the bottom row.

Example 2

panel=[[0, 0, 0, 1], [0, 0, 1, 0], [0, 1, 0, 0], [1, 1, 1, 0]] → 4

The anti-diagonal from the top-right corner to the bottom-left one has 4 bulbs.

Example 3

panel=[[0, 0], [0, 0]] → 0

No bulb is lit, so the answer is 0.

Constraints

1 ≤ len(panel), len(panel[i])
len(panel) · len(panel[0]) ≤ 10⁵
All rows have the same length
panel[i][j] is 0 or 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Dynamic Programming Matrix

Similar problems

Warehouse Cart Routes Medium Cheapest Corner-to-Corner Route Medium Largest Solid Square Medium Best Spot for the Turret Medium Steps to the Nearest Zero Medium

Input

panel=[[1, 0, 1], [0, 1, 1], [1, 0, 1]]

Expected

Run checks the first 3 tests in your browser. Submit checks all 94 tests on the server, hidden ones included.