The Number of Islands problem is a common interview question that involves counting the number of islands in a 2D grid. Each island is made up of connected pieces of land (denoted as '1') surrounded by water (denoted as '0'). The challenge is to count how many separate islands exist in the grid, where an island is formed by horizontally or vertically adjacent lands.
We will discuss multiple ways to solve this problem, explaining their pros and cons. Let's dive into solving this problem using Kotlin.
Problem Definition
Given a 2D binary grid grid, return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. The grid is surrounded by water on all sides.
Example 1:
Input:
[
["1", "1", "1", "1", "0"],
["1", "1", "0", "1", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "0", "0", "0"]
]
Output:
1
Example 2:
Input:
[
["1", "1", "0", "0", "0"],
["1", "1", "0", "0", "0"],
["0", "0", "1", "0", "0"],
["0", "0", "0", "1", "1"]
]
Output:
3
Approach 1: Depth-First Search (DFS)
The most intuitive approach is to use Depth-First Search (DFS). We start from each land cell ('1'), mark it as visited (or change it to water '0'), and recursively check its adjacent cells (up, down, left, right). Every time we find an unvisited land cell, we count it as a new island.
Algorithm:
- Traverse the grid.
- If we find a '1', increment the island count and use DFS to mark the entire island as visited.
- For each DFS, recursively mark the neighboring land cells.
Kotlin Implementation:
fun numIslands(grid: Array<CharArray>): Int {
if (grid.isEmpty()) return 0
var count = 0
// Define DFS function
fun dfs(grid: Array<CharArray>, i: Int, j: Int) {
// Return if out of bounds or at water
if (i < 0 || i >= grid.size || j < 0 || j >= grid[0].size || grid[i][j] == '0') return
// Mark the land as visited
grid[i][j] = '0'
// Visit all 4 adjacent cells
dfs(grid, i + 1, j) // down
dfs(grid, i - 1, j) // up
dfs(grid, i, j + 1) // right
dfs(grid, i, j - 1) // left
}
// Iterate over the grid
for (i in grid.indices) {
for (j in grid[i].indices) {
if (grid[i][j] == '1') {
// Found a new island
count++
dfs(grid, i, j)
}
}
}
return count
}
Time Complexity:
- O(m * n), where
mis the number of rows andnis the number of columns. Each cell is visited once.
Space Complexity:
- O(m * n) in the worst case (if the entire grid is land), as we may need to store all cells in the call stack due to recursion.
Approach 2: Breadth-First Search (BFS)
We can also use Breadth-First Search (BFS). Instead of using recursion like in DFS, we use a queue to explore all adjacent cells iteratively. The process is similar, but the main difference lies in the order of exploration.
Algorithm:
- Start from an unvisited land cell ('1').
- Use a queue to explore all adjacent land cells and mark them as visited.
- Each BFS initiation represents a new island.
Kotlin Implementation:
fun numIslands(grid: Array<CharArray>): Int {
if (grid.isEmpty()) return 0
var count = 0
val directions = arrayOf(intArrayOf(0, 1), intArrayOf(1, 0), intArrayOf(0, -1), intArrayOf(-1, 0))
fun bfs(i: Int, j: Int) {
val queue: LinkedList<Pair<Int, Int>>= LinkedList()
queue.offer(Pair(i, j))
grid[i][j] = '0' // Mark the starting cell as visited
while (queue.isNotEmpty()) {
val (x, y) = queue.poll()
for (dir in directions) {
val newX = x + dir[0]
val newY = y + dir[1]
if (newX in grid.indices && newY in grid[0].indices && grid[newX][newY] == '1') {
grid[newX][newY] = '0' // Mark as visited
queue.offer(Pair(newX, newY))
}
}
}
}
for (i in grid.indices) {
for (j in grid[i].indices) {
if (grid[i][j] == '1') {
count++
bfs(i, j)
}
}
}
return count
}
Time Complexity:
- O(m * n), where
mis the number of rows andnis the number of columns. Each cell is visited once.
Space Complexity:
- O(m * n), which is required for the queue in the worst case.
Approach 3: Union-Find (Disjoint Set)
The Union-Find (or Disjoint Set) approach is another efficient way to solve this problem. The idea is to treat each land cell as an individual component and then union adjacent land cells. Once all unions are complete, the number of islands is simply the number of disjoint sets.
Algorithm:
- Initialize each land cell as a separate island.
- For each neighboring land cell, perform a union operation.
- The number of islands will be the number of disjoint sets.
Kotlin Implementation:
class UnionFind(private val m: Int, private val n: Int) {
private val parent = IntArray(m * n) { it }
fun find(x: Int): Int {
if (parent[x] != x) parent[x] = find(parent[x]) // Path compression
return parent[x]
}
fun union(x: Int, y: Int) {
val rootX = find(x)
val rootY = find(y)
if (rootX != rootY) parent[rootX] = rootY
}
fun getCount(): Int {
return parent.count { it == it }
}
}
fun numIslands(grid: Array<CharArray>): Int {
if (grid.isEmpty()) return 0
val m = grid.size
val n = grid[0].size
val uf = UnionFind(m, n)
for (i in grid.indices) {
for (j in grid[i].indices) {
if (grid[i][j] == '1') {
val index = i * n + j
// Try to union with adjacent cells
if (i + 1 < m && grid[i + 1][j] == '1') uf.union(index, (i + 1) * n + j)
if (j + 1 < n && grid[i][j + 1] == '1') uf.union(index, i * n + (j + 1))
}
}
}
val islands = mutableSetOf<Int>()
for (i in grid.indices) {
for (j in grid[i].indices) {
if (grid[i][j] == '1') {
islands.add(uf.find(i * n + j))
}
}
}
return islands.size
}
Time Complexity:
- O(m * n), as we perform a union operation for each adjacent land cell.
Space Complexity:
- O(m * n) for the union-find parent array.
Calling in main():
fun main() {
val grid1 = arrayOf(
charArrayOf('1', '1', '1', '1', '0'),
charArrayOf('1', '1', '0', '1', '0'),
charArrayOf('1', '1', '0', '0', '0'),
charArrayOf('0', '0', '0', '0', '0')
)
println("Number of Islands : ${numIslands(grid1)}") // Output: 1
val grid2 = arrayOf(
charArrayOf('1', '1', '0', '0', '0'),
charArrayOf('1', '1', '0', '0', '0'),
charArrayOf('0', '0', '1', '0', '0'),
charArrayOf('0', '0', '0', '1', '1')
)
println("Number of Islands : ${numIslands(grid2)}") // Output: 3
}Which Solution is Best?
-
DFS/BFS (Approaches 1 & 2): These are the simplest and most intuitive solutions. Both have a time complexity of O(m * n), which is optimal for this problem. DFS uses recursion, which might run into issues with large grids due to stack overflow, but BFS avoids this problem by using an iterative approach. If you want simplicity and reliability, BFS is preferred.
-
Union-Find (Approach 3): This approach is more advanced and has a similar time complexity of O(m * n). However, it can be more difficult to understand and implement. It also performs well with path compression and union by rank, but for this problem, the DFS/BFS approach is usually sufficient and easier to implement.
Conclusion
For this problem, BFS is the recommended solution due to its iterative nature, which avoids recursion issues with large grids, while still being efficient and easy to understand.
Full Problem description in LeetCode
Thank you for reading my latest article! I would greatly appreciate your feedback to improve my future posts. 💬 Was the information clear and valuable? Are there any areas you think could be improved? Please share your thoughts in the comments or reach out directly. Your insights are highly valued. 👇😊. Happy coding! 💻✨
Posts
