Created
November 16, 2016 23:20
-
-
Save arcesino/cf2dd3dbdfc4c1e9d1b25b33905ad99b to your computer and use it in GitHub Desktop.
Find largest island in a matrix
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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