Count the one islands in the matrix

Question

What is an island? A group of connected 1s forms an island. For example, the below matrix contains 5 islands:

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

I'm looking for code review, best practices, optimizations etc.

public final class CountIslands {

    private CountIslands() {}

    private static enum Direction {
        NW(-1, -1), N(0, -1), NE(-1, 1), E(0, 1), SE(1, 1), S(1, 0), SW(1, -1), W(-1, 0);

        int rowDelta;
        int colDelta;

        Direction(int rowDelta, int colDelta) {
            this.rowDelta = rowDelta;
            this.colDelta = colDelta;
        }

        public int getRowDelta() {
            return rowDelta;
        }

        public int getColDelta() {
            return colDelta;
        }
    }

    private static boolean isValid(int newRow, int newCol, Direction direction, int[][] m, boolean[][] visited) {
        // visited was constructed from matrix so we are sure that checking visitor for row lengh would do no harm.
        if (newRow < 0 || newRow >= visited.length) return false;
        if (newCol < 0 || newCol >= visited[0].length) return false;
        if (visited[newRow][newCol]) return false;
        return m[newRow][newCol] == 1;
    }

    private static void dfs(int row, int col, int[][] m, boolean[][] visited) {
        visited[row][col] = true;
        for (Direction direction : Direction.values()) {
            int newRow = row + direction.getRowDelta();
            int newCol = col + direction.getColDelta();
            if (isValid(newRow, newCol, direction, m, visited)) {
                dfs(newRow, newCol, m, visited);
            }
        }
    }

    /**
     * Returns the number of 1 islands.
     * 
     * @param m     the input matrix
     * @return      the number of 1 islands.
     */
    public static int count(int[][] m) {
        final boolean[][] visited = new boolean[m.length][m[0].length];
        int count = 0;

        for (int row = 0; row < m.length; row++) {
            for (int col = 0; col < m[0].length; col++) {
                if (m[row][col] == 1 && !visited[row][col]) {
                    dfs(row, col, m, visited);
                    count++;
                }
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] m = { { 1, 1, 0, 0 }, { 0, 0, 0, 1 }, { 0, 0, 1, 1 } };

        System.out.println("Expected 2, Actual " + count(m));

        int[][] m1 = { { 1, 1, 0, 0 }, { 0, 0, 1, 1 }, { 0, 0, 1, 1 } };

        System.out.println("Expected 1, Actual " + count(m1));

    }
}

Answer 1

So, I looked at the problem spec, expecting to see a 3-word description o the title of the problem, and not much else, followed by 'Looking for optimizations, and confirmation that compelxity is O(n log(n) ).

Fortunately, I was disappointed ;-) Your description is improved over previous questions, and I can actually follow it without having to google-search for references and hints. It would have been improved slightly if you had spelled out carefully that diagonally touching 1 values combine to form an island... but this is a nit-pick.

Then, I did the normal-for-me task of thinking 'How would I solve this', and I thought for a moment, and decided I would:

1. scan the matrix cell-by-cell
2. if you encounter a 1, use recursion to follow all it's adjacent 1 values
3. mark all visited cells as 'seen'
4. consider that process a 'hit' for an island
5. scan the remaining unseen cells for the next unseen island. (go to 1).

So, I looked through your code, and, it took me a moment, but I found all of those processes in your solution.

So, you have solved this the same way I would have tackled it. The algorithm is 'good', and all that is then left, is to look at how you have implemented it...

• I like the Enum for the directions. It is a good solution.
• I think your variable names have improved recently. I much prefer seeing row and col instead of x and y, etc. It is more descriptive, and it helps.
• count() could be countIslands() because that is what is being counted.

That's a pretty short list of nit-picky things. In all, this is a good program.

There is one suggestion I have for your recursion, and that is that there are multiple 'styles' of recursive methods. If you choose one method, and use it consistently (except for those times the other methods are better), it helps. My suggestion is that you should settle on what I call optimistic recursion.... which is the opposite case of what Wikipedia calls 'short-circuit recursion'. What I am saying, is that 'standard' recursion checks the recursive state, and, if it is valid, it does it's work, and it then calls recursion. The short-circuit system does the state-check of the new state before recursing in to that new state.

By way of example, a standard (what I call optimistic) recursion for this problem would be:

private static void dfs(int row, int col, int[][] m, boolean[][] visited) {
    // check recursion state... and expect it to have failures.
    if (row < 0 || row >= m.length || col < 0 || col >= m[0].length) {
        // invalid state, index-out-of-bounds
        return;
    }
    // OK, row/column are valid... more checks
    if (visited[row][col]) {
        // already seen this valid position.
        return;
    }
    // mark the position seen
    visited[row][col] = true;
    // if it's not an island....
    if (0 == m[row][col]) {
       return;
    }
    // OK, we are still on the island, let's optimistically search around....
    for (Direction direction : Direction.values()) {
        dfs(row + direction.getRowDelta(), col + direction.getColDelta(), m, visited);
    }
}

This optimistic approach simplifies the call structure significantly.... (and eliminates the isValid() method).

Food for thought.

Finally, I don't like calling your method dfs.... it's not a depth-first-search.... since that applies to a tree. The 'cells' in the 'landscape' are not linked in a tree structure, as one cell could be a neighbour to many other cells. A better name would be scan, or even just search.

Answer 2

Besides what @rolfl has said, I only have one nit-pick. I consider this to be a pretty big one though.

Put this at the beginning of your main method:

Direction.NW.rowDelta = 4;
Direction.S.colDelta = -2;

Congratulations, you have now screwed up your program!

Switching the deltas for any direction should not be allowed, it should not compile. To make it that way, you have to add private final to your field declarations in your enum (Technically you only need final but it never hurts to put in private there as well)

private final int colDelta;
private final int rowDelta;

After making that change and trying to modify the deltas from anywhere, you will see that there is the compiler error that we all love!

Besides this, I have only good things to say. I like your Direction enum, it is good enough to be a public enum in a completely separate file actually - I believe you can re-use it for other purposes. It was very easy to understand your question, your code is overall well written. Good job.