2
\$\begingroup\$

This solution surpassed 100% of submissions for efficiency! My method was to recursively check surrounding values and change any contiguous "land" to "water". Is there a better way to write what I wrote?

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

class Solution {
public int numIslands(char[][] grid) {
    int islands = 0;

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

    return islands;
}

public void destroyIsland(char[][] grid, int i, int j) {
    grid[i][j] = '0';
    if (i < grid.length - 1 && grid[i+1][j] == '1') {
        destroyIsland(grid, i+1, j);
    }
    if (i > 0 && grid[i-1][j] == '1') {
        destroyIsland(grid, i-1, j);
    }
    if (j < grid[i].length - 1 && grid[i][j+1] == '1') {
        destroyIsland(grid, i, j+1);
    }
    if (j > 0 && grid[i][j-1] == '1') {
        destroyIsland(grid, i, j-1);
    }
}
}
\$\endgroup\$
1
\$\begingroup\$

The code seems correct. The only missing part is

You may assume all four edges of the grid are all surrounded by water.

which means that numIslands may iterate

    for (int i = 1; i < grid.length - 1; i++) {
        for (int j = 1; j < grid[i].length - 1; j++) {

and do not bother destroyIsland with validating the surroundings.

\$\endgroup\$
  • \$\begingroup\$ I interpreted that as "all cells outside the bounds should be interpreted as water", which makes the original correct and yours faulty. \$\endgroup\$ – Mark Jeronimus Jan 26 at 9:46
  • \$\begingroup\$ @MarkJeronimus, you are correct. This solution would not pass the test. \$\endgroup\$ – Ned Redmond Feb 2 at 3:08

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.