Maximum islands

Tag: Palantir http://www.1point3acres.com/bbs/thread-143763-1-1.html

1 2 0 0

3 0 4 0

0 1 0 1

Max = 1 + 2 + 3

public int maxiumnIslands(int[][] grid) {
    if (grid==null || grid.length==0 || grid[0].length==0) return 0;
    int M = grid.length;
    int N = grid[0].length;
    int maxNum = 0;

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            int num = 0;
            if (grid[i][j] != 0) {
                num = vistAndCountIsland(grid, i, j);
            }
            maxNum = Math.max(num, maxNum);
        }
    }

    return maxNum;
}

private int vistAndCountIsland(int[][] grid, int i, int j) {
    if (i >= 0 && j >= 0 && i < grid.length && j < grid[0].length) {
        if (grid[i][j] == 0) {
            return 0;
        } else {
            int count = grid[i][j];
            grid[i][j] = 0;

            return count
                    + vistAndCountIsland(grid, i + 1, j)
                    + vistAndCountIsland(grid, i - 1, j)
                    + vistAndCountIsland(grid, i, j - 1)
                    + vistAndCountIsland(grid, i, j + 1);
        }
    }
    return 0;
}

Follow up 1：What if negative number

Follow up 2：Convert to iterative approach

Using queues to store next elements to visit.

public int maxiumnIslandsIterative(int[][] grid) {
    if (grid==null || grid.length==0 || grid[0].length==0) return 0;
    int M = grid.length;
    int N = grid[0].length;
    int maxNum = 0;
    Queue<Integer> queueRow = new LinkedList();
    Queue<Integer> queueCol = new LinkedList();

    for (int i = 0; i < M; i++) {
        for (int j = 0; j < N; j++) {
            int num = 0;
            if (grid[i][j] != 0) {
                queueRow.offer(i);
                queueCol.offer(j);

                while (!queueRow.isEmpty()) {
                    int ii = queueRow.poll();
                    int jj = queueCol.poll();

                    if (ii >= 0 && jj >= 0 && ii < grid.length && jj < grid[0].length) {
                        if (grid[ii][jj] != 0) {
                            int count = grid[ii][jj];
                            grid[ii][jj] = 0;
                            num += count;

                            queueRow.offer(ii + 1); queueCol.offer(jj);
                            queueRow.offer(ii - 1); queueCol.offer(jj);
                            queueRow.offer(ii); queueCol.offer(jj + 1);
                            queueRow.offer(ii); queueCol.offer(jj - 1);
                        }
                    }
                }
                maxNum = Math.max(num, maxNum);
            }
        }
    }
    return maxNum;
}