Longest sequence of same subsequent number in a square matrix Given an N-by-N grid with each cell either occupied by an 'X', an 'O', or empty, write a program to find the longest sequence of consecutive 'X's either horizontal, vertically, or diagonally. To test your program, you can create a random grid where each cell contains an 'X' or 'O' with probability 1/3.

I would like a review of my answer. I'm not sure it's efficient enough, or even efficient at all. I chose to use numbers for now since they easier to work with. I hope it's all clear. 

class Main {
    public static void main(String[] args){
        int n = 4;
        int[][] grid = new int[n][n];
        int max =  Integer.MIN_VALUE;

        for(int i = 0; i &lt; n; i++){
            for(int j = 0; j &lt; n; j++){

                // three nums are produced. there is 1/3 chance for each.
                int r = (int)(Math.random()*3);

                // both 'X' and 'O' have 1/3 chance to be produced. 
                if(r == 1) grid[i][j] = 1;
                if(r == 2) grid[i][j] = 2;

                System.out.print(grid[i][j]+" ");
            }
            System.out.println();
        }

        // horizontal, vertical, backward diag, forward diag
        int hori  = 0, vert = 0, bdia = 0, fdia = 0;

        // assuming 1 represents 'X' and 2 represents 'O'
        int num   = (int)(1 + Math.random()*2);

        for(int i = 0; i &lt; n; i++){
            hori = 0; vert = 0;
            // horizontal instances  
            for(int j = 0; j &lt; n; j++){
                if(grid[i][j] != num)
                    hori = 0;
                else hori ++;
                max = hori &gt; max? hori: max;
            }

            // vertical  instances 
            for(int j = 0; j &lt; n; j++){
                if(grid[j][i] != num)
                    vert = 0;
                else vert ++;
                max = vert &gt; max? vert: max;
            }

            // forward diag instances (fdia)
            for(int j = 0; j &lt; n &amp;&amp; i == 0; j++){
                if(grid[j][j] != num)
                    fdia = 0;
                else fdia ++;
                max = fdia &gt; max? fdia: max;
            }

            // backward diag instances (bdia) 
            for(int j = 0; j &lt; n &amp;&amp; i == 0; j++){
                if(grid[j][n-1-j] != num)
                    bdia = 0;
                else bdia ++;
                max = bdia &gt; max? bdia: max;
            }
        }

        System.out.println("max : "+max);
        System.out.println("num : "+num);
    }
}
Let me start out by saying that your solution certainly is efficient enough. You only loop over the grid once to do the 4 checks. And don't check the same sequence twice. (like going left to right AND right to left).

Since this is codereview.stackexchange let's instead start by reviewing the code :)



First of all, there is a mistake in your solution. Diagonally is not the same as on the main diagonals. The simplest example that you won't find in your solution but what I believe does count as a normal diagonal sequence is the following:


  O X O
  O O X
  O O O


This looks like a sequence of lenght 2 to me.



I dissagree with you when you say:


  I chose to use numbers for now since they easier to work with.  


We can just as well work with char:

char[][] grid = new char[n][n];
...
if(r == 1) grid[i][j] = 'X';
if(r == 2) grid[i][j] = 'O';
...
if(grid[i][j] == 'X')


Doing this also makes it explicit that you're only checking for the X without having to arbitrarily choose if the 'X' is represented by a 1 or a 2 in your grid.



You have put all the code inside the main method. Although it kinda works for this small problem, it's generally a better idea to split your code up into more manageable blocks.

A few easy ones to separate are a grid generator, and a method to print a grid. By splitting this up into 2 functions we can also provide a fixed grid and still print that grid as well.

Printing is easy. We take the same loops as you already have with the same System.out... calls. But without the random setting of the cell.

public static void printGrid(char[][] grid){
    for(int row = 0; row &lt; grid.length; row++){
        for(int col = 0; col &lt; grid[0].length; col++){
            System.out.print(grid[row][col]+" ");
        }
        System.out.println();
    }
}


Notice how I named the loop variables row and col to make it clear what we're looping over.

Randomly generating a grid isn't much harder. We use the same loops, but now we randomly choose one of 3 characters. I'm using _ to represent "emtpy".

public static char[][] generateRandomGrid(int size){
    char[][] grid = new char[size][size];
    for(int row = 0; row &lt; grid.length; row++){
        for(int col = 0; col &lt; grid[0].length; col++){
            // three nums are produced. there is 1/3 chance for each.
            int r = (int)(Math.random()*3);

            // both 'X' and 'O' have 1/3 chance to be produced. 
            if(r == 0) {
                grid[row][col] = '_';
            }
            if(r == 1) {
                grid[row][col] = 'X';
            }
            if(r == 2) {
                grid[row][col] = 'O';
            }
        }
    }
    return grid;
}


Now for the actual checking of the sequences. This part of your code confused me. You have the outer loop with index i. Then depending on what you check the meaning of this i changes to the row/the column/something you ignore entirely.

Instead let's provide 4 specific methods, that each calculate the maximum sequence in a specific direction for a given grid.

The horizontal one is easy. It's basically what you already did:

public static int findMaxHorizontalSequence(char[][] grid){
    int max = 0;
    for(int row = 0; row &lt; grid.length; row ++) {
        int currentSeq = 0;
        for(int col = 0; col &lt; grid[0].length; col ++){
            if(grid[row][col] == 'X'){
                currentSeq ++;
                if(currentSeq &gt; max){
                    max = currentSeq;
                }
            } else {
                currentSeq = 0;
            }
        }
    }
    return max;
}


The vertical check is almost the same, except the for loops are swapped.

public static int findMaxVerticalSequence(char[][] grid){
    int max = 0;
    for(int col = 0; col &lt; grid[0].length; col++){
        int currentSeq = 0;
        for(int row = 0; row &lt; grid.length; row ++){
            if(grid[row][col] == 'X'){
                currentSeq ++;
                if(currentSeq &gt; max){
                    max = currentSeq;
                }
            } else {
                currentSeq = 0;
            }
        }
    }
    return max;
}


You might have noticed by now that I always use grid.length and grid[0].length. This is so that the functions will all work correctly even if the grid was a rectangular shape instead of a square.

For the diagonals we'll have to do a bit more work. The easiest is probably to split it up in 2 loops. One for each of the following lines of starting locations:

X X X ?        O O O O  
O O O O        X O O O  
O O O O        X O O O  
O O O O        ? O O O  


We can ignore the spots with a ?. Those diagonals are only 1 char long, so it will already be counted by the horizontal/vertical checks. No need to repeat this.

The code could look like this:

public static int findMaxDownRightSequence(char[][] grid) {
    int max = 0;
    for (int startRow = 0; startRow &lt; grid.length - 1; startRow++) {
        int currentSeq = 0;
        for (int row = startRow, col = 0; row &lt; grid.length &amp;&amp; col &lt; grid[0].length; row++, col++) {
            if (grid[row][col] == 'X') {
                currentSeq++;
                if (currentSeq &gt; max) {
                    max = currentSeq;
                }
            } else {
                currentSeq = 0;
            }
        }
    }
    for (int startCol = 1; startCol &lt; grid[0].length - 1; startCol++) {
        int currentSeq = 0;
        for (int row = 0, col = startCol; row &lt; grid.length &amp;&amp; col &lt; grid[0].length; row++, col++) {
            if (grid[row][col] == 'X') {
                currentSeq++;
                if (currentSeq &gt; max) {
                    max = currentSeq;
                }
            } else {
                currentSeq = 0;
            }
        }
    }
    return max;
}


But at this point I really start noticing that I'm copy-pasting a lot. This usually means that we should refactor some common code. The common part of the code that we're copy-pasting is the part inside the inner for loop:

if (grid[row][col] == 'X') {
    currentSeq++;
    if (currentSeq &gt; max) {
        max = currentSeq;
    }
} else {
    currentSeq = 0;
}


We have to find how to make the for loop work for all cases.
This means: for( find initial values for row and col ; check if they are still within the bounds of the grid ; and find how they change each step. )

Let's write a method that gets all those parameters and figure out how to map the existing ones to this method. And let's also write a specific method to check if the row and col are within the bounds of the grid, because otherwise the for statement will become unreadable.

public static int maxSequence(char[][] grid, int startRow, int startCol, 
                              int verticalDir, int horizontalDir){
    int currentSeq = 0;
    int max = 0;
    for(int row = startRow, col = startCol; 
                checkBounds(grid, row, col); 
                row += verticalDir, col += horizontalDir) {
        if (grid[row][col] == 'X') {
            currentSeq++;
            if (currentSeq &gt; max) {
                max = currentSeq;
            }
        } else {
            currentSeq = 0;
        }
    }
    return max;
}

private static boolean checkBounds(char[][] grid, int row, int col) {
    return row &gt; 0 &amp;&amp; col &gt; 0 &amp;&amp; row &lt; grid.length &amp;&amp; col &lt; grid[0].length;
}


Now we can rewrite our other methods. The outer for loops stay the same, but we replace the inner loops with a call to our new method:

public static int findMaxHorizontalSequence(char[][] grid) {
    int max = 0;
    for (int row = 0; row &lt; grid.length; row++) {
        int rowMax = maxSequence(grid, row, 0, 0, 1);
        if(rowMax &gt; max){
            max = rowMax;
        }
    }
    return max;
}

public static int findMaxVerticalSequence(char[][] grid) {
    int max = 0;
    for (int col = 0; col &lt; grid[0].length; col++) {
        int colMax = maxSequence(grid, 0, col, 1, 0);
        if(colMax &gt; max){
            max = colMax;
        }
    }
    return max;
}

public static int findMaxDownRightSequence(char[][] grid) {
    int max = 0;
    for (int startRow = 0; startRow &lt; grid.length - 1; startRow++) {
        int diagMax = maxSequence(grid, startRow, 0, 1, 1);
        if(diagMax &gt; max){
            max = diagMax;
        }
    }
    for (int startCol = 1; startCol &lt; grid[0].length - 1; startCol++) {
        int currentSeq = maxSequence(grid, 0, startCol, 1, 1);
        if (currentSeq &gt; max) {
            max = currentSeq;
        }
    }
    return max;
}


All that's left is to write a method for the other diagonal.

    public static int findMaxDownLeftSequence(char[][] grid) {
    int max = 0;
    for (int startRow = 0; startRow &lt; grid.length-1; startRow++) {
        int diagMax = maxSequence(grid, startRow, grid.length, 1, -1);
        if(diagMax &gt; max){
            max = diagMax;
        }
    }
    for (int startCol = 1; startCol &lt; grid[0].length; startCol++) {
        int currentSeq = maxSequence(grid, ?, ?, ?, ?);
        if (currentSeq &gt; max) {
            max = currentSeq;
        }
    }
    return max;
}


Since this site requires working code in the first place to review I didn't want to give you the full solution for the diagonals. So try to fill in the four ? in the last part to see if you fully understood the solution :)



To run the new code (and find out if you filled in the last part correctly) you can use the following main method:

public static void main(String[] args) throws Exception {
    char[][] grid = new char[][]{{'O', 'X', 'O'},
            {'X', 'O', 'O'},
            {'O', 'O', 'O'}};
    printGrid(grid);
    System.out.println(findMaxSequence(grid));
}


or you can replace the grid with

char[][] grid = generateRandomGrid(100);


To test it out on a random grid.

Fun fact: on my PC it takes between 3.5 and 4 seconds to find the solution of a randomly generated 10000 x 10000 grid. About the same time it takes to randomly generate the grid.

I doubt it can get much faster on a single thread solution. Since you're stuck with looping over the entire grid anyway.