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.
Flowchart Walkthrough
Let's analyze Leetcode 200. Number of Islands using the algorithm flowchart. Here's a detailed breakdown using the provided Flowchart:
Is it a graph?
- Yes: The matrix can be interpreted as a graph with each cell representing a node, and edges between cells that are directly adjacent and both land.
Is it a tree?
- No: Although there are no explicit cycles given in the grid representation as a graph, the presence of multiple separated groups of connected land cells implies it is not strictly a tree structure since there could be multiple "root" nodes (i.e., multiple unconnected groups of islands).
Is the problem related to directed acyclic graphs (DAGs)?
- No: The problem focuses on counting the number of connected components (islands), not on properties specific to directed acyclic graphs.
Is the problem related to shortest paths?
- No: The goal is not to find the shortest path but to count distinct land areas surrounded by water.
Does the problem involve connectivity?
- Yes: The core of the problem is to explore all connected components (islands) in the grid.
Is the graph weighted?
- No: Connections between the nodes (cells in the grid) do not have weights; they are either adjacent (1, indicating land) or they are not (0, indicating water).
Conclusion: Although the flowchart leads to BFS in cases of unweighted connectivity problems, this specific problem is commonly solved using DFS to count the number of connected components effectively. Depth-First Search is ideal here for exploring each land cell and marking all connected cells recursively until all lands making up an island have been visited. The same reasoning through the flowchart applies, but DFS is often preferred for simplicity in implementation and natural stack recursion fitting the problem's requirements.
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:
- Iterate over each cell of the grid.
- When a cell with value '1' is found, increment our island count as we've discovered a new island.
- Initiate a DFS from that cell, changing all connected '1's (i.e., the entire island) to '0's to mark them as visited.
- 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:
-
Define a nested function called
dfs
inside thenumIslands
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. -
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. -
Then, for each adjacent direction defined by
dirs
(which are the four possible movements: up, down, left, and right), thedfs
function calculates the adjacent cell's coordinates(x, y)
. -
If the adjacent cell
(x, y)
is within the grid boundaries (0 <= x < m
and0 <= y < n
) and it's a '1' (land), thedfs
function is recursively called for this new cell. -
Outside of the
dfs
function, the main part of thenumIslands
method initializes anans
counter to keep track of the number of islands found. -
The variable
dirs
is a tuple containing the directions used in the DFS to traverse the grid in a cyclic order. By usingpairwise(dirs)
, we always get a pair of directions that represent a straight line movement (either horizontal or vertical) without diagonal moves. -
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 theans
counter since we have identified an entire island. -
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.
-
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Imagine we are given the following grid:
grid = [ ["1","1","0","0","0"], ["1","1","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
Here is a step-by-step walkthrough of the solution approach for the given example:
-
We start from the top-left corner of the grid and iterate through each cell.
-
The first cell
grid[0][0]
is '1', indicating land, so we increase our island count to1
. -
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)
changesgrid[0][0]
to '0'. It then recursively explores its neighbors which aregrid[0][1]
,grid[1][0]
(sincegrid[-1][0]
andgrid[0][-1]
are out of bounds).dfs(0, 1)
changesgrid[0][1]
to '0'. Its neighborsgrid[0][2]
andgrid[1][1]
are then explored but they are already '0' and '1' respectively but sincegrid[1][1]
is connected,dfs(1, 1)
is called.dfs(1, 1)
changesgrid[1][1]
to '0'. There are no more '1's connected to it directly.
This results in the grid becoming:
[ ["0","0","0","0","0"], ["0","0","0","0","0"], ["0","0","1","0","0"], ["0","0","0","1","1"] ]
-
Continuing the iteration, we find the next '1' at
grid[2][2]
. We increment our island count to2
and performdfs(2, 2)
which results in:[ ["0","0","0","0","0"], ["0","0","0","0","0"], ["0","0","0","0","0"], ["0","0","0","1","1"] ]
-
Finally, the last '1' is encountered at
grid[3][3]
. After incrementing the island count to3
, we performdfs(3, 3)
which also changesgrid[3][4]
to '0' as it is connected:[ ["0","0","0","0","0"], ["0","0","0","0","0"], ["0","0","0","0","0"], ["0","0","0","0","0"] ]
With no more '1's left in the grid, we have identified all the islands - a total of
3
. -
Now that we have processed the entire grid, we return the
ans
counter value which is3
.
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
1class Solution:
2 def numIslands(self, grid: List[List[str]]) -> int:
3 def dfs(row, col):
4 # Mark the current cell as '0' to indicate the land is visited
5 grid[row][col] = '0'
6 # Explore all four directions from the current cell
7 for dx, dy in zip(directions[:-1], directions[1:]):
8 new_row, new_col = row + dx, col + dy
9 # Check if the new cell is within grid bounds and is land ('1')
10 if 0 <= new_row < rows and 0 <= new_col < cols and grid[new_row][new_col] == '1':
11 # Perform DFS on the new cell
12 dfs(new_row, new_col)
13
14 # Initialize count of islands
15 island_count = 0
16 # Define the directions to explore
17 directions = (-1, 0, 1, 0, -1)
18 # Get the dimensions of the grid
19 rows, cols = len(grid), len(grid[0])
20 # Iterate over each cell in the grid
21 for row in range(rows):
22 for col in range(cols):
23 # If the cell is land ('1'), it's a new island
24 if grid[row][col] == '1':
25 # Perform DFS to mark all connected land for the current island
26 dfs(row, col)
27 # Increment the island count
28 island_count += 1
29 # Return the total number of islands
30 return island_count
31
1class Solution {
2 // Define grid and its dimensions
3 private char[][] grid;
4 private int numRows;
5 private int numCols;
6
7 // Method to count the number of islands in the given grid
8 public int numIslands(char[][] grid) {
9 numRows = grid.length;
10 numCols = grid[0].length;
11 this.grid = grid;
12
13 int numIslands = 0; // Initialize island count
14
15 // Iterate through each cell in the grid
16 for (int i = 0; i < numRows; ++i) {
17 for (int j = 0; j < numCols; ++j) {
18 // If cell contains '1', it is part of an island
19 if (grid[i][j] == '1') {
20 // Use DFS to mark the entire island as visited
21 depthFirstSearch(i, j);
22 // Increase the island count
23 ++numIslands;
24 }
25 }
26 }
27 return numIslands;
28 }
29
30 // Helper method to perform DFS to mark all cells of an island as visited
31 private void depthFirstSearch(int row, int col) {
32 // Mark the current cell as visited by setting it to '0'
33 grid[row][col] = '0';
34
35 // Array to facilitate the exploration of adjacent directions (up, right, down, left)
36 int[] directions = {-1, 0, 1, 0, -1};
37
38 // Explore all 4 adjacent directions
39 for (int k = 0; k < 4; ++k) {
40 int newRow = row + directions[k];
41 int newCol = col + directions[k + 1];
42 // Check boundaries and if the adjacent cell is part of an island
43 if (newRow >= 0 && newRow < numRows && newCol >= 0 && newCol < numCols && grid[newRow][newCol] == '1') {
44 // Continue DFS exploration for the adjacent cell
45 depthFirstSearch(newRow, newCol);
46 }
47 }
48 }
49}
50
1#include <vector>
2#include <functional>
3using namespace std;
4
5class Solution {
6public:
7 // Function to count the number of islands in a given grid
8 int numIslands(vector<vector<char>>& grid) {
9 int rowCount = grid.size(); // Number of rows in the grid
10 int colCount = grid[0].size(); // Number of columns in the grid
11 int islandCount = 0; // Number of islands found
12
13 // Directions array for moving up, right, down, left
14 int directions[5] = {-1, 0, 1, 0, -1};
15
16 // Depth-First Search (DFS) to traverse the island and mark visited parts
17 function<void(int, int)> dfs = [&](int row, int col) {
18 grid[row][col] = '0'; // Mark the current cell as visited
19 // Traverse adjacent cells
20 for (int k = 0; k < 4; ++k) {
21 int newRow = row + directions[k];
22 int newCol = col + directions[k + 1];
23 // Check if the new position is within bounds and has a '1' (unvisited land)
24 if (newRow >= 0 && newRow < rowCount && newCol >= 0 && newCol < colCount && grid[newRow][newCol] == '1') {
25 dfs(newRow, newCol); // Recursively call DFS for the adjacent cell
26 }
27 }
28 };
29
30 // Iterate through the entire grid
31 for (int row = 0; row < rowCount; ++row) {
32 for (int col = 0; col < colCount; ++col) {
33 // If the cell contains a '1', it is a new island
34 if (grid[row][col] == '1') {
35 dfs(row, col); // Perform DFS to mark all connected lands
36 islandCount++; // Increment island count
37 }
38 }
39 }
40 return islandCount; // Return the total count of islands
41 }
42};
43
1function numIslands(grid: string[][]): number {
2 // m is the number of rows in the grid
3 const numberOfRows = grid.length;
4 // n is the number of columns in the grid (assuming the grid is not empty)
5 const numberOfColumns = grid[0].length;
6 // ans will hold the number of islands found
7 let numberOfIslands = 0;
8
9 // The Depth-First Search function, which marks visited land sections as '0'
10 function depthFirstSearch(row: number, column: number) {
11 // Set the current location to '0' to mark as visited
12 grid[row][column] = '0';
13 // Array representing the 4 directions (up, right, down, left)
14 const directions = [-1, 0, 1, 0, -1];
15
16 // Iterate over each direction
17 for (let k = 0; k < 4; ++k) {
18 // Calculate the new coordinates based on the current direction
19 const newRow = row + directions[k];
20 const newColumn = column + directions[k + 1];
21
22 // Check if the new coordinates are within bounds and the cell contains '1'
23 if (newRow >= 0 && newRow < numberOfRows && newColumn >= 0 && newColumn < numberOfColumns && grid[newRow][newColumn] === '1') {
24 // If so, perform DFS on the adjacent cell
25 depthFirstSearch(newRow, newColumn);
26 }
27 }
28 }
29
30 // Iterate over every cell in the grid
31 for (let row = 0; row < numberOfRows; ++row) {
32 for (let column = 0; column < numberOfColumns; ++column) {
33 // If the cell contains '1' (land), an island is found
34 if (grid[row][column] === '1') {
35 // Perform DFS to mark the entire island
36 depthFirstSearch(row, column);
37 // Increment the island count
38 numberOfIslands++;
39 }
40 }
41 }
42
43 // Return the total number of islands found
44 return numberOfIslands;
45}
46
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.
Which type of traversal does breadth first search do?
Recommended Readings
https algomonster s3 us east 2 amazonaws com cover_photos dfs svg Depth First Search Prereqs Recursion Review problems recursion_intro Trees problems tree_intro With a solid understanding of recursion under our belts we are now ready to tackle one of the most useful techniques in coding interviews Depth First Search DFS
https algomonster s3 us east 2 amazonaws com cover_photos bfs svg Breadth First Search on Trees Hopefully by this time you've drunk enough DFS Kool Aid to understand its immense power and seen enough visualization to create a call stack in your mind Now let me introduce the companion spell
Union Find Disjoint Set Union Data Structure Introduction Prerequisite Depth First Search Review problems dfs_intro Once we have a strong grasp of recursion and Depth First Search we can now introduce Disjoint Set Union DSU This data structure is motivated by the following problem Suppose we have sets of elements
Want a Structured Path to Master System Design Too? Donāt Miss This!