LC: Longest Line of Consecutive One in Matrix - spiralgo/algorithms GitHub Wiki

Longest Line of Consecutive One in Matrix

The Essence:

Besides the first element of some line, each tile will by definition will have some another one in the (opposite) direction of the line. Using this knowledge, there are two main methods of counting a line only once:

1. Count the line only when the line starts. Other tiles check their directions to see if a counting should be done in that direction.
2. Store the length of the line, increment it when the respective next tile is one, count for the the total when the line ends.

Details:

For the first method, a tile can simply check if it has another tile in its vertical, horizontal, diagonal and anti-diagonal directions. Each tile can also be marked with a flag after it has been traversed for the first time to prevent this, which is another approach.

For the second method, dynamic programming can be used, since new tiles will optimally add on to the previous solutions. For this current horizontal, vertical, and diagonal lengths need to be logically kept.

The implementation of these approaches can be found here: https://github.com/spiralgo/algorithms/tree/master/src/main/java/algorithms/curated170/medium/longestlineofconsecutiveoneinmatrix