Problem Explanation: Given a 2D grid map of ‘1’s (land) and ‘0’s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example:
Input: [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Input: [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3Expected Time Complexity: O(m*n), where m is the number of rows and n is the number of columns in the grid.
Expected Space Complexity: O(m*n), where m is the number of rows and n is the number of columns in the grid.
Constraints:
- The input grid will only contain ‘0’s and ‘1’s.
- The dimensions of the input grid will be at most 300×300.
Kotlin Solution:
Kotlin
fun numIslands(grid: Array<CharArray>): Int {
val m = grid.size
val n = grid[0].size
var count = 0
fun dfs(row: Int, col: Int) {
if (row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == '0') {
return
}
grid[row][col] = '0' // mark the current cell as visited
dfs(row - 1, col) // search up
dfs(row + 1, col) // search down
dfs(row, col - 1) // search left
dfs(row, col + 1) // search right
}
for (i in 0 until m) {
for (j in 0 until n) {
if (grid[i][j] == '1') {
count++
dfs(i, j)
}
}
}
return count
}
fun main() {
val grid = 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(numIslands(grid)) // 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(numIslands(grid2)) // Output: 3
}