Number of Islands

Question

Given a 2D grid of '1's (land) and '0's (water), count the number of islands. Tests BFS/DFS on grids, one of Google's most frequently asked problems.

Codemia · Accepted Answer

The problem of counting the number of islands in a 2D grid is best solved using Depth-First Search (DFS) or Breadth-First Search (BFS). Here, the grid is composed of '1's representing land and '0's representing water. The DFS/BFS approach is applicable because we need to explore all connected '1's (land) starting from any unvisited '1', marking them as visited by changing them to '0's or using a visited set. This method allows us to traverse the entire island and count it as one before moving on to find other islands. 1. Initialize a counter to track the number of islands. 2. Iterate through each cell in the 2D grid. 3. When a '1' is found, increment the island counter. 4. Perform a DFS or BFS from that cell to visit all connected '1's (land) and mark them as visited (by setting them to '0'). 5. Continue this process until all cells are checked. **Example:** Given the grid: ``` 11000 11000 00100 00011 ``` - Start at (0,0): it's '1', count an island and mark connected '1's. - Visit (0,1), (1,0), (1,1) while marking them. - Move to (2,0): it's '0', skip. - Move to (2,2): it's '1', count another island and mark (2,2), (3,2), (3,3), (3,4). - Result: 2 islands. Here is the Python solution using DFS: ```python def numIslands(grid): if not grid: return 0 rows, cols = len(grid), len(grid[0]) def dfs(r, c): if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] == '0': return grid[r][c] = '0' # Mark as visited dfs(r+1, c) # down dfs(r-1, c) # up dfs(r, c+1) # right dfs(r, c-1) # left island_count = 0 for r in range(rows): for c in range(cols): if grid[r][c] == '1': island_count += 1 dfs(r, c) return island_count ``` This function iterates through each cell, counts islands, and uses DFS to mark connected land. The time complexity of this solution is O(M * N), where M is the number of rows and N is the number of columns in the grid. This is because in the worst case, we might visit every cell in the grid. The space complexity is O(M * N) in the case of the recursion stack for DFS in the worst case where the grid is filled with '1's, as we could be storing up to M*N calls on the stack. 1. An empty grid: The function should return 0. 2. A grid with all water ('0's): It should also return 0. 3. A grid with all land ('1's): It should return 1. 4. A grid with multiple separate islands: Ensure that the algorithm correctly counts them. 5. Very thin grids (1xN or Nx1): Check if it handles edge cases where the grid is a single row or column.

Number of Islands

Google

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

Google Software Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string