How do you solve Number of Islands on LeetCode?

Number of Islands (LeetCode #200) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(n) space complexity. Key insight: Islands are formed by connected '1's.

What is the brute force solution for Number of Islands?

The brute force approach for Number of Islands is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves checking each cell in the grid to see if it's land ('1'). If it is, we can perform a depth-first search (DFS) to mark all connected land cells as visited. This way, we can count how many separate islands exist. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Number of Islands?

Number of Islands uses the following concepts: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix. The recommended patterns to study are: Depth-First Search, Breadth-First Search, Graph Traversal.

What are the interview tips for Number of Islands?

Explain your thought process clearly. Consider edge cases, such as empty grids. Be prepared to discuss time and space complexity.

What are common mistakes when solving Number of Islands?

Not marking visited cells, leading to infinite loops. Confusing horizontal and vertical connections.

#200

Number of Islands

Medium

ArrayDepth-First SearchBreadth-First SearchUnion-FindMatrixDepth-First SearchBreadth-First SearchGraph Traversal

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(n)

💡

Intuition

Time O(n)Space O(n)

The optimal solution uses a breadth-first search (BFS) or depth-first search (DFS) to explore the grid. This approach is efficient because we only traverse each land cell once, marking it as visited, which avoids redundant checks.

⚙️

Algorithm

4 steps

1Step 1: Initialize a counter for islands.
2Step 2: Loop through each cell in the grid.
3Step 3: If a cell is '1', increment the island counter and perform BFS/DFS to mark all connected '1's as visited.
4Step 4: Continue until all cells are checked.

solution.py24 lines

1# Full working Python code
2class Solution:
3    def numIslands(self, grid):
4        if not grid:
5            return 0
6        self.rows, self.cols = len(grid), len(grid[0])
7        count = 0
8        for r in range(self.rows):
9            for c in range(self.cols):
10                if grid[r][c] == '1':
11                    count += 1
12                    self.bfs(grid, r, c)
13        return count
14    
15    def bfs(self, grid, r, c):
16        queue = [(r, c)]
17        grid[r][c] = '0'
18        while queue:
19            x, y = queue.pop(0)
20            for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
21                nx, ny = x + dx, y + dy
22                if 0 <= nx < self.rows and 0 <= ny < self.cols and grid[nx][ny] == '1':
23                    grid[nx][ny] = '0'
24                    queue.append((nx, ny))

ℹ

Complexity note: The time complexity is O(n) since we visit each cell in the grid once. The space complexity is O(n) due to the queue used for BFS, which could store all cells in the worst case.

1Islands are formed by connected '1's.
2DFS/BFS can efficiently explore and mark connected components.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.