Problem description:

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:

1
2
3
4
11110
11010
11000
00000

Output: 1

Example 2:

Input:

1
2
3
4
11000
11000
00100
00011

Output: 3

Solution:

The idea is to treat the 2d grid map as an undirected graph and there is an edge between two horizontally or vertically adjacent nodes of value 1.

Linear scan the 2d grid map, if a node contains a 1, then it is a root node that triggers a Depth First Search. During DFS, every visited node should be set as 0 to mark as visited node. Count the number of root nodes that trigger DFS, this number would be the number of islands since each DFS starting at some root identifies an island.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid, i, j):
            grid[i][j] = '-'
            if i-1 >= 0 and grid[i-1][j] == "1": dfs(grid, i-1, j)
            if i+1 < len(grid) and grid[i+1][j] == "1": dfs(grid, i+1, j)
            if j-1 >= 0 and grid[i][j-1] == "1": dfs(grid, i, j-1)
            if j+1 < len(grid[0]) and grid[i][j+1] == "1": dfs(grid, i, j+1)
            return
            
        res = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1":
                    res += 1
                    dfs(grid, i, j)
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
private:
    void dfs(vector<vector<char>>& grid, int r, int c) {
        int nr= grid.size();
        int nc= grid[0].size();
      
          grid[r][c] = '0'; //we already check this island on outer loop, so mark it out
          if(r-1 >= 0 && grid[r-1][c]== '1') dfs(grid, r-1, c); //check if there's any connected '1', mark it out too
          if(r+1 < nr && grid[r+1][c]== '1') dfs(grid, r+1, c); //mark them out is because we already count on outer loop
          if(c-1 >= 0 && grid[r][c-1]== '1') dfs(grid, r, c-1);
          if(c+1 < nc && grid[r][c+1]== '1') dfs(grid, r, c+1);
    }

public:
    int numIslands(vector<vector<char>>& grid) {
          int nr= grid.size();
          if(!nr) return 0;

          int nc= grid[0].size();
          int num_island= 0;

          for(int r= 0; r< nr; r++){
              for(int c= 0; c< nc; c++){
                  if(grid[r][c] == '1'){
                      ++num_island; //count this first appear island
                      dfs(grid, r, c);
                  }
              }
          }
          return num_island;
    }
};

time complexity: O(mn)
space complexity: O(mn), in worst case the grid is filled with island, DFS goes m*n deep

Solution: Union Find

Create array parent, the size is grid size. It’s to log the parent for grid[i][j]

Calculate the number of 1 at the beginning, then decrease the number when we union an island.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        row, col = len(grid), len(grid[0])
        if not row or not col:
            return 0
        
        self.count = sum(grid[i][j] == '1' for i in range(row) for j in range(col))
        parent = [i for i in range(row*col)]
        
        def find(x):
            if parent[x] != x:
                return find(parent[x])
            return parent[x]
        
        def union(x, y):
            xroot, yroot = find(x), find(y)
            if xroot == yroot: return 
            parent[xroot] = yroot
            self.count -= 1
        
        
        # update the parent when we see 1 in grid
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '0':
                    continue
                index = i*col + j
                if i+1 < row and grid[i+1][j] == '1':
                    union(index, index + col)
                if j+1 < col and grid[i][j+1] == '1':
                    union(index, index + 1)
        return self.count

reference:
https://goo.gl/S4Hig9