problem562

package
Version: v1.6.5 Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Mar 23, 2021 License: MIT Imports: 0 Imported by: 0

README

< Previous                  Next >

562. Longest Line of Consecutive One in Matrix (Medium)

Given a 01 matrix M, find the longest line of consecutive one in the matrix. The line could be horizontal, vertical, diagonal or anti-diagonal.

Example:

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

Hint: The number of elements in the given matrix will not exceed 10,000.

[Array]

Hints

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.

Documentation

The Go Gopher

There is no documentation for this package.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
t or T : Toggle theme light dark auto
y or Y : Canonical URL