We can travese and calculate the area of each island, then return the maximum area. We can use either DFS or BFS to traverse the grid.
private val visited = 2
fun maxAreaOfIsland(grid: Array<IntArray>): Int {
var maxArea = 0
for (i in 0 until grid.size) {
for (j in 0 until grid[0].size) {
if (grid[i][j] == 1) {
val currentArea =
// bfs(grid, i, j)
dfs(grid, i, j)
maxArea = if (currentArea > maxArea) currentArea else maxArea
}
}
}
return maxArea
}
private fun dfs(grid: Array<IntArray>, x: Int, y: Int): Int {
val m = grid.size
val n = grid[0].size
if (x !in 0 until m || y !in 0 until n ) return 0
if (grid[x][y] != 1) return 0
grid[x][y] = visited
var area = 1
directions.forEach { d ->
val newX = x + d[0]
val newY = y + d[1]
area += dfs(grid, newX, newY)
}
return area
}
private fun bfs(grid: Array<IntArray>, sourceX: Int, sourceY: Int): Int {
val m = grid.size
val n = grid[0].size
val queue = ArrayDeque<Pair<Int, Int>>()
queue.addLast(sourceX to sourceY)
grid[sourceX][sourceY] = visited
var area = 0
while (queue.isNotEmpty()) {
val (x, y) = queue.removeFirst()
area++
for (d in directions) {
val newX = x + d[0]
val newY = y + d[1]
if (newX !in 0 until m || newY !in 0 until n || grid[newX][newY] != 1) continue
queue.addLast(newX to newY)
grid[newX][newY] = visited
}
}
return area
}- Time Complexity:
O(m * n). - Space Complexity:
O(m * n)for queue or recursive call stack.