Skip to content

Instantly share code, notes, and snippets.

@reyou
Created May 24, 2018 02:19
Show Gist options
  • Save reyou/1528ecd56029c492a3b5dee9c157746d to your computer and use it in GitHub Desktop.
Save reyou/1528ecd56029c492a3b5dee9c157746d to your computer and use it in GitHub Desktop.
// * Find max connected component in an image
// https://www.geeksforgeeks.org/find-number-of-islands/
// https://www.geeksforgeeks.org/find-the-number-of-islands-set-2-using-disjoint-set/
// https://leetcode.com/problems/number-of-islands/description/
// https://leetcode.com/problems/number-of-islands/discuss/131474/Clean-javascript-solution-using-DFS
// https://leetcode.com/problems/number-of-islands/discuss/131165/Detailed-Explanation-of-the-Java-solution
var input = [
[1, 1, 1, 1, 0],
[1, 1, 0, 1, 0],
[1, 1, 0, 0, 0],
[0, 0, 0, 0, 0]
];
var input2 = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]
];
// Number of islands is: 5
let rowCount = input.length;
let colCount = input[0].length;
function findIslands(input, rowCount, colCount) {
let total = 0;
for (let i = 0; i < rowCount; i++) {
for (let j = 0; j < colCount; j++) {
if (input[i][j] === 1) {
search(input, i, j);
total++;
}
}
}
return total;
}
function search(input, row, col) {
if (
row < 0 ||
col < 0 ||
row > rowCount - 1 ||
col > colCount - 1 ||
input[row][col] === 0
) {
return;
}
input[row][col] = 0;
search(input, row - 1, col);
search(input, row, col + 1);
search(input, row + 1, col);
search(input, row, col - 1);
}
console.log(findIslands(input, rowCount, colCount));
console.log(findIslands(input2, rowCount, colCount));
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment