How to Solve the Number of Islands Problem [with Solutions in Python + JavaScript]
Introduction to the Number of Islands Problem
Introduction to the Number of Islands Problem
The Number of Islands problem involves identifying contiguous land as represented on a two-dimensional grid. The grid is composed of 1s and 0s, where 1s represent land and 0s represent water, so solutions to this problem require a grasp of traversal algorithms such as depth-first search, breadth-first search, and union-find.
An Example of the Number of Islands Interview Question
An Example of the Number of Islands Interview Question
Given a 2D matrix, where "1" represents land and "0" represents water, count how many islands are present. An island is a contiguous piece of land, where cells are connected by at least one of four cardinal directions (up, down, left, right), surrounded by water. We can assume the space beyond the borders is water.
Input: grid = [ ["0","0","1","1","0"], ["1","1","1","1","0"], ["0","1","0","0","0"], ["0","0","0","0","0"] ] Output: 1
Input: grid = [ ["1","0","1","1","1"], ["0","0","1","1","0"], ["0","1","0","0","0"], ["0","0","0","1","1"] ]
Output: 3
Constraints
1 <= grid.length <= 1001 <= grid.length[i] <= 100
How to Find the Number of Islands [with Solutions in Java, Python & JavaScript]
How to Find the Number of Islands [with Solutions in Java, Python & JavaScript]
This is a commonly given matrix problem, but it demands some creative problem solving. Although the solutions to this problem leverage some relatively common algorithms, how you communicate your thought process when choosing to apply them is a big part of what an interviewer will be assessing.
Like with all complex problems, let's start by first approaching the problem naively. To determine which cells are land, our algorithm will necessarily need to traverse the entire matrix in order to check the value of each element. Therefore, we can't do better than linear time, which in the case of a two-dimensional matrix, is O(n * m).
While traversing the matrix, how do we track the number of clusters of "1"s and determine which land belongs to which islands? Remember that two adjacent “1”s are part of the same island, so if we were to traverse using two nested loops, starting from the top-left and ending at the bottom-right, we'll likely visit land later in the iteration that belongs to an island that was previously discovered. In this case, we would need a way to know what island a particular land cell belongs to. We would also need to know when an island is fully explored so we can add to our number of islands tally.
To avoid this, let's consider exhausting the exploration of each island once a piece of land is encountered, and once complete, we can simply add 1 to our running count of islands. We know for certain that an island is surrounded by water, so we would just need a way to explore all adjacent lands until there are none left.
What kind of traversal algorithm would be useful to discover all adjacent lands? A useful mental model here is that a matrix can be expressed using a graph data structure. While there are many ways to represent a graph computationally, a two-dimensional matrix lends itself well to a highly structured and connected graph: we can imagine that each element in a matrix is a graph node, connected via edges to its adjacent elements, moving left, up, right, down, and sometimes diagonally. You might see where this is going - we can use common graph traversal algorithms to our advantage: depth-first search (DFS) and breadth-first search (BFS).
Once a "1" is encountered, we can treat this as a "root" node and perform a traversal over each adjacent "1" until exhaustion. We'll also need to mark these elements as already-visited, since we know these land cells belong to an already accounted-for island. We can either track where we've been with a set of coordinates, or just transform visited lands into water so they are "ignored" as the iteration continues. Once an island exploration is complete, we increment our tally of numbers of islands, and simply continue the linear scan until another "1" is discovered.
Approach 1: Depth-First Search (DFS)
Depth-first search (DFS) is an essential arrow in an engineer's problem-solving quiver. While there are many implementations, it is at its core a recognizable recursive algorithm (one that can also be expressed using a stack) that includes:
- a base case to stop the recursion -> if the cell we are trying to visit is out of bounds or a water cell.
- a way to know where to go next -> we want to check all adjacent cells (up, right, down, left).
For our island search, we'll perform a linear scan over the 2-dimensional grid with two nested for-loops, and if a cell is water we'll kick off our DFS, making sure to mark all waters as land so we never revisit. In the end, we are essentially just counting the number of times DFS is called from within the scope of the two for-loops.
class Solution:
def dfs(self, row: int, col: int, grid: List[List[str]]):
# base case
if self.is_inbounds(grid, row, col):
# transform land into water so we don't revisit this cell.
grid[row][col] = "0"
for new_row, new_col in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
self.dfs(new_row, new_col, grid)
# validation: row and col are within the grid and the cell is a land.
def is_inbounds(self, grid: List[List[str]], row: int, col: int) -> bool:
return row >= 0 and row < len(grid) and col >= 0 and col < len(grid[0]) and grid[row][col] == "1"
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
num_rows = len(grid)
num_cols = len(grid[0])
for row in range(0, num_rows):
for col in range(0, num_cols):
if grid[row][col] == "1":
count += 1
self.dfs(row, col, grid)
return count
1class Solution:
2 def dfs(self, row: int, col: int, grid: List[List[str]]):
3 # base case
4if self.is_inbounds(grid, row, col):
5 # transform land into water so we don't revisit this cell.
6 grid[row][col] = "0"
7
8 for new_row, new_col in [(row - 1, col), (row + 1, col), (row, col - 1), (row, col + 1)]:
9 self.dfs(new_row, new_col, grid)
10
11 # validation: row and col are within the grid and the cell is a land.
12 def is_inbounds(self, grid: List[List[str]], row: int, col: int) -> bool:
13 return row >= 0 and row < len(grid) and col >= 0 and col < len(grid[0]) and grid[row][col] == "1"
14
15 def numIslands(self, grid: List[List[str]]) -> int:
16 count = 0
17 num_rows = len(grid)
18 num_cols = len(grid[0])
19
20 for row in range(0, num_rows):
21 for col in range(0, num_cols):
22 if grid[row][col] == "1":
23 count += 1
24 self.dfs(row, col, grid)
25
26 return count
27Time/Space Complexity
- Time complexity:
O(n * m), wherenis the number of rows andmis the number of columns. - Space complexity:
O(m * n). In the worst case, where the entire grid is filled with lands, the call stack will grow to the number of cells in the grid.
Approach 2: Breadth-First Search (BFS)
Breadth-first search (BFS) in this case accomplishes the same goal as DFS - exhausting all adjacent water cells - but through a different mechanism. Instead of always going to the furthest edges of the island when traversing, BFS explores all adjacent cells first, sort of like a single level, before moving on. This is accomplished using a queue, so that the order in which cells are visited remains level-by-level.
Like our DFS solution, we'll still need to mark visited lands by transforming them into water, and we'll ultimately tally the number of islands by counting how many times BFS is initiated from the linear nested for-loop scan.
class Solution:
# validation: row and col are within the grid and the cell is a land.
def is_inbounds(self, grid: List[List[str]], row: int, col: int) -> bool:
return row >= 0 and row < len(grid) and col >= 0 and col < len(grid[0]) and grid[row][col] == "1"
def bfs(self, row: int, col: int, grid: List[List[str]]):
q = collections.deque()
q.append((row, col))
grid[row][col] = "0"
while q:
# visit the node
row, col = q.popleft()
for new_row, new_col in [(row + 1, col), (row, col + 1), (row - 1, col), (row, col - 1)]:
if self.is_inbounds(grid, new_row, new_col):
grid[new_row][new_col] = "0"
q.append((new_row, new_col))
def numIslands(self, grid: List[List[str]]) -> int:
count = 0
num_rows = len(grid)
num_cols = len(grid[0])
for row in range(0, num_rows):
for col in range(0, num_cols):
if grid[row][col] == "1":
count += 1
self.bfs(row, col, grid)
return count
1class Solution:
2 # validation: row and col are within the grid and the cell is a land.
3 def is_inbounds(self, grid: List[List[str]], row: int, col: int) -> bool:
4 return row >= 0 and row < len(grid) and col >= 0 and col < len(grid[0]) and grid[row][col] == "1"
5
6 def bfs(self, row: int, col: int, grid: List[List[str]]):
7 q = collections.deque()
8 q.append((row, col))
9 grid[row][col] = "0"
10
11 while q:
12 # visit the node
13 row, col = q.popleft()
14
15 for new_row, new_col in [(row + 1, col), (row, col + 1), (row - 1, col), (row, col - 1)]:
16 if self.is_inbounds(grid, new_row, new_col):
17 grid[new_row][new_col] = "0"
18 q.append((new_row, new_col))
19
20 def numIslands(self, grid: List[List[str]]) -> int:
21 count = 0
22 num_rows = len(grid)
23 num_cols = len(grid[0])
24
25 for row in range(0, num_rows):
26 for col in range(0, num_cols):
27 if grid[row][col] == "1":
28 count += 1
29 self.bfs(row, col, grid)
30
31 return count
32Time/Space Complexity
- Time complexity:
O(n * m), wherenis the number of rows andmis the number of columns. - Space complexity:
O(min(n, m). In the worst case, where the grid is entirely lands, the size of the queue will be bounded by either the row or column size before cells are processed.
Practice the Number of Islands Problem With Our AI Interviewer
Practice the Number of Islands Problem With Our AI Interviewer
Number of Islands Frequently Asked Questions (FAQ)
Number of Islands Frequently Asked Questions (FAQ)
Number of Islands FAQ
What is an island in a matrix?
An island in a matrix is a contiguous area of land represented by the value '1' and is surrounded by water, which is represented by the value '0'. In a 2D matrix, two land cells are considered connected if they share an edge (horizontally or vertically). An island consists of one or more connected land cells.
Is number of islands a graph problem?
Yes, it's like exploring the land on a map. You can think of the land cells as nodes in a big interconnected network, and we want to find groups of nodes (land cells) that are connected. So, it's a bit like a graph problem. Various graph traversal algorithms, such as Depth-First Search (DFS) or Breadth-First Search (BFS), can be used to solve this problem.
What is the easiest way to solve the number of islands problem?
The easiest way to solve the number of islands problem is by using Depth-First Search (DFS) or Breadth-First Search (BFS). The DFS approach involves recursively exploring adjacent cells of a land cell to mark them as visited while incrementing the island count. The BFS approach, on the other hand, uses a queue to explore connected land cells layer by layer. Both methods are effective in finding and counting the number of islands in the matrix. The choice of algorithm depends on personal preference and how familiar you are with them.
About interviewing.io
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
