Number of Islands

Problem

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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.

Examples

Example 1:

$$ \begin{array}{|c|c|c|c|c|} \hline \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 & \colorbox{blue} 0 \\ \hline \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 & \colorbox{blue} 0 & \colorbox{Chocolate} 1 & \colorbox{blue} 0 \\ \hline \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 \\ \hline \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 \\ \hline \end{array} $$

1
2
3
4
5
6
7


Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:

$$ \begin{array}{|c|c|c|c|c|} \hline \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 \\ \hline \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 \\ \hline \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{Chocolate} 1 & \colorbox{blue} 0 & \colorbox{blue} 0 \\ \hline \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{blue} 0 & \colorbox{Chocolate} 1 & \colorbox{Chocolate} 1 \\ \hline \end{array} $$

1
2
3
4
5
6
7


Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] is '0' or '1'.

Solution

Looks like a graph problem, with finding connected components.

Method 1 - DFS with Sinking of Island

The basic idea of the following solution is merging adjacent lands, and the merging should be done recursively. Involves array modification. We will set values to X, by doing dfs on it till the point we reach the island. Once, done, we check for next 1 which is not yet updated.

Each element is visited once only. So time is O(m*n).

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

 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


public class Solution {
    public int numIslands(char[][] grid) {
		int ans = 0;
        int m = grid.length;
        int n = grid[0].length;
	    
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                if (grid[r][c] == '1') {
                    ans++;
                    dfs(grid, r, c);
                }
            }
        }
	    
        return ans;
    }

    private final int[][] dirs = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

    private void dfs(char[][] grid, int r, int c) {
		if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || 
			grid[r][c] == '0') {
			return; 
		}
		
        grid[r][c] = '0';
		
        for (int[] dir : dirs) {
            dfs(grid, r + dir[0], c + dir[1]);
        }
    }
}

 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


public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int rows = grid.length;
        int cols = grid[0].length;
        int ans = 0;

        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '1') {
                    ans++;
                    dfs(grid, r, c);
                }
            }
        }

        return ans;
    }

    private void dfs(char[][] grid, int r, int c) {
        int rows = grid.length;
        int cols = grid[0].length;

        if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') {
            return;
        }

        grid[r][c] = '0';
        dfs(grid, r+1, c);
        dfs(grid, r-1, c);
        dfs(grid, r, c+1);
        dfs(grid, r, c-1);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        
        m, n = len(grid), len(grid[0])
        ans = 0

        def dfs(r, c):
            if r < 0 or c < 0 or r >= m or c >= n or grid[r][c] == '0':
                return
            grid[r][c] = '0'
            dirs = [(-1, 0), (0, 1), (1, 0), (0, -1)]
            for dr, dc in dirs:
                dfs(r + dr, c + dc)

        for r in range(m):
            for c in range(n):
                if grid[r][c] == '1':
                    ans += 1
                    dfs(r, c)

        return ans

 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


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
            
        # Number of rows and columns
        rows, cols = len(grid), len(grid[0])
        # Island counter
        ans: int = 0

        # DFS function to mark connected lands
        def dfs(r: int, c: int) -> None:
            # If out of bounds or water, stop recursion
            if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] == '0':
                return
            
            # Mark current cell as water so we don't revisit it
            grid[r][c] = '0'
            # Visit all adjacent cells (up, down, left, right)
            dfs(r+1, c)
            dfs(r-1, c)
            dfs(r, c+1)
            dfs(r, c-1)

        # Iterate through the entire grid
        for r in range(rows):
            for c in range(cols):
                # If a land cell is found, start a DFS
                if grid[r][c] == '1':
                    ans += 1  # Increment island count
                    dfs(r, c)  # Mark the entire island

        return ans

Method 2 - BFS and Visited Set

Similar to above approach, but we will use set for visited nodes. Also, we will use queue instead of stack.

Code

 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
45
46
47
48


class Solution {
	public int numIslands(char[][] grid) {
		if (grid == null || grid.length == 0 || grid[0].length == 0)
			return 0;
	
		int m = grid.length;
		int n = grid[0].length;
		Set<Pair<Integer, Integer>> visited = new HashSet<>();
	
		int count = 0;
		for (int i = 0; i<m; i++) {
			for (int j = 0; j<n; j++) {
				if (grid[i][j] == '1' && !visisted.contains(new Pair<>(i, j))) {
					count++;
					bfs(grid, i, j);
				}
			}
		}
	
		return count;
	}
	
	public void bfs(int r, int c, Set<Pair<Integer, Integer>> visited) {
		Queue<Pair<Integer, Integer>> q = new LinkedList<>();
	
		int m = grid.length;
		int n = grid[0].length;
		
		Pair<Integer, Integer> p = new Pair<>(r, c);
		
		visited.push(p);
		q.add(p)
	
		int[] dx = {-1, 1, 0, 0	};
		int[] dy = { 0, 0, -1, 1 };
		while (!q.isEmpty()) {
			for (int k = 0; k<4; k++) {
				int newR = r + dx[k];
				int newC = c + dy[k];
				if (newR >= 0 && newR<m && newC >= 0 && newC<n && grid[x][y] == '1' && !visited.contains(new Pair<>(newR, newC))) {
					q.add(new Pair<>(newR, newC));
					visited.add(new Pair<>(newR, newC));
				}
			}
		}
		
	}
}

Complexity

⏰ Time complexity: O(m*n)
🧺 Space complexity: O(m*n)

Method 3 - Union-Find

Code

 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
45
46
47
48
49
50
51
52
53


public int numIslands(char[][] grid) {
	if (grid == null || grid.length == 0 || grid[0].length == 0)
		return 0;

	int m = grid.length;
	int n = grid[0].length;

	int[] dx = {-1, 1, 0, 0	};
	int[] dy = { 0, 0, -1, 1 };

	int[] root = new int[m * n];

	int count = 0;
	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			if (grid[i][j] == '1') {
				root[i * n + j] = i * n + j;
				count++;
			}
		}
	}

	for (int i = 0; i<m; i++) {
		for (int j = 0; j<n; j++) {
			if (grid[i][j] == '1') {
				for (int k = 0; k<4; k++) {
					int x = i + dx[k];
					int y = j + dy[k];

					if (x >= 0 && x<m && y >= 0 && y<n && grid[x][y] == '1') {
						int cRoot = getRoot(root, i * n + j);
						int nRoot = getRoot(root, x * n + y);
						if (nRoot != cRoot) {
							root[cRoot] = nRoot; //update previous node's root to be current
							count--;
						}

					}
				}
			}
		}
	}

	return count;
}

public int getRoot(int[] arr, int i) {
	while (arr[i] != i) {
		i = arr[arr[i]];
	}

	return i;
}

Complexity

⏰ Time complexity: O(m*n) roughly
🧺 Space complexity: O(m*n)

Problem#

Examples#

Constraints#

Solution#

Method 1 - DFS with Sinking of Island#

Video explanation#

Code#

Method 2 - BFS and Visited Set#

Code#

Complexity#

Method 3 - Union-Find#

Code#

Complexity#

Problem

Examples

Constraints

Solution

Method 1 - DFS with Sinking of Island

Video explanation

Code

Method 2 - BFS and Visited Set

Code

Complexity

Method 3 - Union-Find

Code

Complexity