200. Number of Islands

Problem Description

In this problem, we are provided with a two-dimensional grid where each cell has a binary value; either '1' representing land or '0' representing water. The task is to calculate the number of islands on this grid. An island is defined as a cluster of adjacent '1's, and two cells are considered adjacent if they are directly north, south, east, or west of each other (no diagonal connection). The boundary of the grid is surrounded by water, which means there are '0's all around the grid.

To sum up, we need to identify the groups of connected '1's within the grid and count how many separate groups (islands) are present.

Intuition

The intuition behind the solution is to scan the grid cell by cell. When we encounter a '1', we treat it as a part of an island which has not been explored yet. To mark this exploration, we perform a Depth-First Search (DFS) starting from that cell, turning all connected '1's to '0's, effectively "removing" the island from the grid to prevent counting it more than once.

The core approach involves the following steps:

1. Iterate over each cell of the grid.
2. When a cell with value '1' is found, increment our island count as we've discovered a new island.
3. Initiate a DFS from that cell, changing all connected '1's (i.e., the entire island) to '0's to mark them as visited.
4. Continue the grid scan until all cells are processed.

During the DFS, we explore in four directions: up, down, left, and right. We ensure the exploration step remains within grid bounds to avoid index errors.

This approach allows us to traverse each island only once, and by marking cells as visited, we avoid recounting any part of an island. Thus, we effectively count each distinct island just once, leading us to the correct solution.

Learn more about Depth-First Search, Breadth-First Search and Union Find patterns.

Solution Approach

The solution approach utilizes Depth-First Search (DFS) as the main algorithm for solving the problem of finding the number of islands in the grid. Here's a step-by-step explanation of the implementation:

1. Define a nested function called dfs inside the numIslands method which takes the grid coordinates (i, j) of a cell as parameters. This function will be used to perform the DFS from a given starting cell that is part of an island.

2. The dfs function first sets the current cell's value to '0' to mark it as visited. This prevents the same land from being counted again when iterating over other parts of the grid.

3. Then, for each adjacent direction defined by dirs (which are the four possible movements: up, down, left, and right), the dfs function calculates the adjacent cell's coordinates (x, y).

4. If the adjacent cell (x, y) is within the grid boundaries (0 <= x < m and 0 <= y < n) and it's a '1' (land), the dfs function is recursively called for this new cell.

5. Outside of the dfs function, the main part of the numIslands method initializes an ans counter to keep track of the number of islands found.

6. The variable dirs is a tuple containing the directions used in the DFS to traverse the grid in a cyclic order. By using pairwise(dirs), we always get a pair of directions that represent a straight line movement (either horizontal or vertical) without diagonal moves.

7. We iterate over each cell of the grid using a nested loop. When we encounter a '1', we call the dfs function on that cell, marking the entire connected area, and then increment the ans counter since we have identified an entire island.

8. At the end of the nested loops, we have traversed the entire grid and recursively visited all connected '1's, marking them as '0's, thus avoiding multiple counts of the same land.

9. The ans variable now contains the total number of islands, which is returned as the final answer.

The main data structures used in the implementation are:

• The input grid, which is a two-dimensional list used to represent the map.
• The dirs tuple, which stores the possible directions of movement within the grid.

By using DFS, we apply a flood fill technique, similar to the "bucket" fill tool in paint programs, where we fill an entire connected region with a new value. In our case, we fill connected '1's with '0's to "remove" the island from being counted more than once. This pattern ensures that each separate island is counted exactly one time.

Example Walkthrough

Imagine we are given the following grid:

1grid = [
2    ["1","1","0","0","0"],
3    ["1","1","0","0","0"],
4    ["0","0","1","0","0"],
5    ["0","0","0","1","1"]
6]

Here is a step-by-step walkthrough of the solution approach for the given example:

1. We start from the top-left corner of the grid and iterate through each cell.

2. The first cell grid[0][0] is '1', indicating land, so we increase our island count to 1.

3. We then call the dfs function on this cell which will mark all the connected '1's as '0's as follows:

   • dfs(0, 0) changes grid[0][0] to '0'. It then recursively explores its neighbors which are grid[0][1], grid[1][0] (since grid[-1][0] and grid[0][-1] are out of bounds).
   • dfs(0, 1) changes grid[0][1] to '0'. Its neighbors grid[0][2] and grid[1][1] are then explored but they are already '0' and '1' respectively but since grid[1][1] is connected, dfs(1, 1) is called.
   • dfs(1, 1) changes grid[1][1] to '0'. There are no more '1's connected to it directly.

   This results in the grid becoming:

   1[
   2    ["0","0","0","0","0"],
   3    ["0","0","0","0","0"],
   4    ["0","0","1","0","0"],
   5    ["0","0","0","1","1"]
   6]

4. Continuing the iteration, we find the next '1' at grid[2][2]. We increment our island count to 2 and perform dfs(2, 2) which results in:

   1[
   2    ["0","0","0","0","0"],
   3    ["0","0","0","0","0"],
   4    ["0","0","0","0","0"],
   5    ["0","0","0","1","1"]
   6]

5. Finally, the last '1' is encountered at grid[3][3]. After incrementing the island count to 3, we perform dfs(3, 3) which also changes grid[3][4] to '0' as it is connected:

   1[
   2    ["0","0","0","0","0"],
   3    ["0","0","0","0","0"],
   4    ["0","0","0","0","0"],
   5    ["0","0","0","0","0"]
   6]

   With no more '1's left in the grid, we have identified all the islands - a total of 3.

6. Now that we have processed the entire grid, we return the ans counter value which is 3.

This walkthrough demonstrates the application of DFS in marking each discovered island and preventing overlap in counting by converting all connected '1' cells to '0'. By the completion of the iteration over the entire grid, we have the total number of separate islands encountered.

Solution Implementation

Time and Space Complexity

The given code implements the Depth-First Search (DFS) algorithm to count the number of islands ('1') in a grid. The time complexity and space complexity analysis are as follows:

Time Complexity

The time complexity of the code is O(m * n), where m is the number of rows in the grid, and n is the number of columns. This is because the algorithm must visit each cell in the entire grid once to ensure all parts of the islands are counted and marked. The DFS search is invoked for each land cell ('1') that hasn't yet been visited, and it traverses all its adjacent land cells. Although the outer loop runs for m * n iterations, each cell is visited once by the DFS, ensuring that the overall time complexity remains linear concerning the total number of cells.

Space Complexity

The space complexity is O(m * n) in the worst case. This worst-case scenario occurs when the grid is filled with land cells ('1'), where the depth of the recursion stack (DFS) potentially equals the total number of cells in the grid if we are dealing with one large island. Since the DFS can go as deep as the largest island, and in this case, that's the entire grid, the stack space used by the recursion is proportionate to the total number of cells.

Learn more about how to find time and space complexity quickly using problem constraints.