Skip to content

Instantly share code, notes, and snippets.

@arcesino
Created November 16, 2016 23:20
Show Gist options
  • Save arcesino/cf2dd3dbdfc4c1e9d1b25b33905ad99b to your computer and use it in GitHub Desktop.
Save arcesino/cf2dd3dbdfc4c1e9d1b25b33905ad99b to your computer and use it in GitHub Desktop.
Find largest island in a matrix
val matrix = Array(
Array(0, 1, 0, 0, 1),
Array(0, 1, 1, 1, 1),
Array(1, 0, 1, 1, 0),
Array(1, 1, 0, 0, 1)
)
val rows = matrix.indices
val columns = matrix(0).indices
def getIslandSize(i: Int, j: Int): Int = {
if (!rows.contains(i) || !columns.contains(j) || matrix(i)(j) == 0) {
0
} else {
matrix(i)(j) = 0
1 + getIslandSize(i - 1, j) +
getIslandSize(i, j - 1) +
getIslandSize(i + 1, j) +
getIslandSize(i, j + 1)
}
}
val islandSizes = for {
i <- rows
j <- columns
if matrix(i)(j) == 1
} yield getIslandSize(i, j)
islandSizes.max
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment