3
\$\begingroup\$

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.)

\$\endgroup\$
1
\$\begingroup\$

In worst case (array that has only 1, no 0) you are doing M operations for each cell in MxM for a total of M^3 operations. You can reduce it to M^2 if you remember the results for previous row (for vertical, LD, RD) and current(horizontal). If the cell is 1 increment the counters, otherwise reset them to zero.

\$\endgroup\$
  • \$\begingroup\$ So that means I need 4 global counters (max) and 4 local counters? \$\endgroup\$ – minsanity Sep 24 '18 at 21:47
  • \$\begingroup\$ Also, for vertical counter, how do I remember each column with one counter? \$\endgroup\$ – minsanity Sep 24 '18 at 21:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.