/ Data Structure and Algorithms  

Leetcode 200. Number of Islands

Question



Given a two-dimensional array, 1 as the land and 0 as the sea, connecting the land to form an island. Think of the area outside the array as the sea, and determine how many islands there are.

Similar Questions

Solution

The idea is very simple, we only need to traverse the two-dimensional array. When we meet 1, just mark the current 1 and all the 1s connected to it as 2. Then record how many 1 we have met, which means there are several islands. See the example below.

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
33
34
35
36
37
[1] 1 0 0 0
 1  1 0 0 0
 0 0 1 0 0
 0 0 0 1 1
Meet 1, count = 1;

Mark 1 and all 1s connected to it as 2
2 2 0 0 0
2 2 0 0 0
0 0 1 0 0
0 0 0 1 1

2 2  0  0 0
2 2  0  0 0
0 0 [1] 0 0
0 0  0  1 1
Meet next 1, count = 2;

Mark 1 and all 1s connected to it as 2
2 2 0 0 0
2 2 0 0 0
0 0 2 0 0
0 0 0 1 1   

2 2 0  0  0
2 2 0  0  0
0 0 2  0  0
0 0 0 [1] 1  
Meet next 1, count = 3;

Mark 1 and all 1s connected to it as 2
2 2 0 0 0
2 2 0 0 0
0 0 2 0 0
0 0 0 2 2  

No more 1, so the number of islands =  count = 3

Another problem is how to mark all connected 1s. It is also very straightforward. We can directly do a DFS using recursion.

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
33
34
35
36
37
38
39
40
41
42
43
44
public int numIslands(char[][] grid) {
    int result = 0;

    // total number of rows
    int rows = grid.length;

    if (rows == 0) {
        return result;
    }

    // total number of columns
    int columns = grid[0].length;

    // loop all points
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j < columns; j++) {
            if (grid[i][j] == '1') {
                result++;

                mark(i, j, rows, columns, grid);
            }
        }

    }

    return result;
}

// mark all '1' connected with grid[curRow][curCol] as '2'
private void mark(int curRow, int curCol, int totalRow, int totalCol, char[][] grid) {
    // reach boundary or the point is not '1'
    if (curRow == -1 || curCol == -1 || curRow == totalRow || curCol == totalCol || grid[curRow][curCol] != '1') {
        return;
    }

    // mark as '2'
    grid[curRow][curCol] = 2;

    // expand up, down, left, right
    mark(curRow - 1, curCol, totalRow, totalCol, grid);
    mark(curRow + 1, curCol, totalRow, totalCol, grid);
    mark(curRow, curCol - 1, totalRow, totalCol, grid);
    mark(curRow, curCol + 1, totalRow, totalCol, grid);
}