Number of Islands

Question: 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.

Example 1:

Input:
11110
11010
11000
00000
Output: 1

You may view the full question here.

Approach 1: Initially this seemed like a graph problem, that needed the nodes to be linked to one another. But I found a simple enough, yet efficient approach using the matrix as is in this post. Honestly, it appears that the code is already in a great shape and it is best to preserve it as is —

//Approach 1
//Runtime: 1ms
//Memory usage: 42MB
class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0; i<grid.length; i++){
            for(int j = 0; j<grid[0].length; j++){
                if(grid[i][j]=='1'){
                    count++;
                    markIsland(grid, i, j);
                }
            }
        }
        return count;
    }
    
    private void markIsland(char[][] grid, int i, int j){
        if(i<0 || i>=grid.length || j<0 || j>=grid[0].length || grid[i][j]!='1'){
            return;
        }
        grid[i][j] = 'X';
        markIsland(grid, i-1, j);
        markIsland(grid, i+1, j);
        markIsland(grid, i, j-1);
        markIsland(grid, i, j+1);
    }
}

Find more posts here.

Cheers & Chao!