# Find the longest line in 2D (MxM) array (vertical, horizontal, or diagonal)

Find the length of the longest line with given square (MxM) matrix. (vertical, horizontal, or diagonal allowed) (Length of the longest line = number of consecutive 1's)

i.e.) input:

{
{0,0,0,0,0,0,0,0},
{0,0,1,0,1,0,0,0},
{0,1,0,1,0,0,0,0},
{1,1,1,1,1,1,1,0},
{0,1,0,0,0,1,0,0},
{1,1,0,0,0,0,1,0},
{0,1,0,0,0,0,0,1},
{0,0,0,0,0,0,0,0}
}


output: 7 (The 4th horizontal row is the longest line in this case.)

My java code:

public class LongestLine {
private int hmax = 0;
private int vmax = 0;
private int rdmax = 0; // right down direction
private int ldmax = 0; // left down direction

public int longestLine(int[][] grid) {

for(int i = 0; i < grid.length; i++) {
for(int j = 0; j < grid[i].length; j++) {
if(grid[i][j] == 1) update(grid, i, j);
}
}

return Math.max(Math.max(hmax, vmax), Math.max(rdmax, ldmax));
}

private void update(int[][] grid, int i, int j) {
int h = 1, v = 1, rd = 1, ld = 1;

if(j < grid[i].length - 1 && grid[i][j+1] == 1) {
if(j == 0 || grid[i][j-1] != 1) h = updateH(grid, i, j+1, h);
}
if(i < grid.length - 1 && grid[i+1][j] == 1) {
if(i == 0 || grid[i-1][j] != 1) v = updateV(grid, i+1, j, v);
}
if(j < grid[i].length - 1 && i < grid.length - 1 && grid[i+1][j+1] == 1) {
if(j == 0 || i == 0 || grid[i-1][j-1] != 1) rd = updateRD(grid, i+1, j+1, rd);
}
if(j > 0 && i < grid.length - 1 && grid[i+1][j-1] == 1) {
if(j == grid[i].length - 1 || i == 0 || grid[i-1][j+1] != 1) ld = updateLD(grid, i+1, j-1, ld);
}

hmax = Math.max(h, hmax);
vmax = Math.max(v, vmax);
rdmax = Math.max(rd, rdmax);
ldmax = Math.max(ld, ldmax);
}

private int updateH(int[][] grid, int i, int j, int h) {
h++;
if(j < grid[i].length - 1 && grid[i][j+1] == 1) h = updateH(grid, i, j+1, h);
return h;
}

private int updateV(int[][] grid, int i, int j, int v) {
v++;
if(i < grid.length - 1 && grid[i+1][j] == 1) v = updateV(grid, i+1, j, v);
return v;
}

private int updateRD(int[][] grid, int i, int j, int rd) {
rd++;
if(j < grid[i].length - 1 && i < grid.length - 1 && grid[i+1][j+1] == 1)
rd = updateRD(grid, i+1, j+1, rd);
return rd;
}

private int updateLD(int[][] grid, int i, int j, int ld) {
ld++;
if(j > 0 && i < grid.length - 1 && grid[i+1][j-1] == 1)
ld = updateLD(grid, i+1, j-1, ld);
return ld;
}
}


My code seems to work, but I'm not sure if this is the most efficient code. Do you think this is OK? Or are there any faster/simpler implementation? (Answer in Java format preferred.)