Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return 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 1:
Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
Output: 1
Example 2:
Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Output: 3
Solution (Depth First Search)
class NumberOfIslands {
constructor(grid, land = '1', water = '0') {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
this.land = land;
this.water = water;
}
/**
* Check whether or not the coordinate is the land
*
* @param number i
* @param number j
* @return boolean
* @time complexity: O(1)
* @space complexity: O(1)
*/
isLand(i, j) {
return (
i >= 0 &&
i < this.rows &&
j >= 0 &&
j < this.cols &&
this.grid[i][j] === this.land
);
}
/**
* Depth First Search
* Change the current coordinate to water
* Find all its adjacent lands and change it to water
* Repeat the above until there is no more land
*
* @param number i
* @param number j
* @time complexity: O(M * N) where M and N corresponds to the number of rows and columns
* @space complexity: O(M * N) where M and N corresponds to the number of rows and columns
*/
dfs(i, j) {
// Make sure it is the land
if (!this.isLand(i, j)) {
return;
}
// Change land to water
this.grid[i][j] = this.water;
// Loop through its adjacent lands
for (const [x, y] of NumberOfIslands.DIRECTIONS) {
this.dfs(i + x, j + y);
}
}
/**
* Get total number of islands
*
* @return number
* @time complexity: O(M * N) where M and N corresponds to the number of rows and columns
* @space complexity: O(M * N) where M and N corresponds to the number of rows and columns
*/
getNumberOfIslands() {
let numOfIslands = 0;
for (let i = 0; i < this.rows; i++) {
for (let j = 0; j < this.cols; j++) {
// Check if the current coordinate is the land
if (this.isLand(i, j)) {
// Change the whole land to water
this.dfs(i, j);
// Increment the number of islands
numOfIslands++;
}
}
}
return numOfIslands;
}
}
NumberOfIslands.DIRECTIONS = [
[-1, 0], // Up
[ 0, 1], // Right
[ 1, 0], // Down
[ 0,-1], // Left
];
Solution (Breath First Search)
Replace the above dfs function with the dfs function below.
/**
* Breath First Search
* Change the current coordinate to water
* Find all its adjacent lands and change it to water
* Repeat the above until there is no more land
*
* @param number i
* @param number j
* @time complexity: O(M * N) where M and N corresponds to the number of rows and columns
* @space complexity: O(M * N) where M and N corresponds to the number of rows and columns
*/
bfs(i, j) {
const queue = [[i, j]];
while (queue.length) {
const [x, y] = queue.pop();
this.grid[x][y] = this.water;
for (const [dx, dy] of NumberOfIslands.DIRECTIONS) {
if (this.isLand(x + dx, y + dy)) {
queue.push([x + dx, y + dy]);
}
}
}
}
Solution (Union Find)
class NumberOfIslandsUnionFind {
constructor(grid, land = '1', water = '0') {
this.grid = grid;
this.rows = grid.length;
this.cols = grid[0].length;
this.land = land;
this.water = water;
this.parents = {};
this.numberOfIslands = 0;
this.numberOfLands = 0;
this.run();
}
/**
* Check whether or not the coordinate is the land
*
* @param number i
* @param number j
* @return boolean
* @time complexity: O(1)
* @space complexity: O(1)
*/
isLand(i, j) {
return (
i >= 0 &&
i < this.rows &&
j >= 0 &&
j < this.cols &&
this.grid[i][j] === this.land
);
}
/**
* Get vertex's root
*
* @param string u
* @return string
* @time complexity: O(1)
* @space complexity: O(1)
*/
find(u) {
if (this.parents[u] === undefined) {
this.parents[u] = u;
} else if (this.parents[u] !== u) {
this.parents[u] = this.find(this.parents[u]);
}
return this.parents[u];
}
/**
* Connect two vertex in a group
*
* @param string u
* @param string v
* @time complexity: O(1)
* @time complexity: O(1)
*/
union(u, v) {
const p1 = this.find(u);
const p2 = this.find(v);
if (p1 === p2) {
return;
}
this.parents[p1] = p2;
this.numberOfIslands++;
}
/**
* Change the current coordinate to water
* Find all its neighbor lands and change it to water
* Repeat the above until there is no more land
*
* @return number
* @time complexity: O(M * N) where M and N corresponds to the number of rows and columns
* @space complexity: O(M * N) where M and N corresponds to the number of rows and columns
*/
traverse(i, j) {
let id = i * this.rows + j;
this.grid[i][j] = this.water;
this.union(id, id);
this.numberOfLands++;
for (const [x, y] of NumberOfIslandsUnionFind.DIRECTIONS) {
const r = i + x;
const c = j + y;
const nextId = r * this.rows + c;
if (this.isLand(r, c)) {
this.union(id, nextId);
}
}
}
/**
* Find lands and connect each other in a group
*
* @time complexity: O(M * N) where M and N corresponds to the number of rows and columns
* @space complexity: O(M * N) where M and N corresponds to the number of rows and columns
*/
run() {
for (let i = 0; i < this.rows; i++) {
for (let j = 0; j < this.cols; j++) {
if (this.grid[i][j] === this.land) {
this.traverse(i, j);
}
}
}
}
/**
* Get the total number of islands
*
* @return number
*/
getNumberOfIslands() {
return this.numberOfLands - this.numberOfIslands;
}
}
NumberOfIslandsUnionFind.DIRECTIONS = [
[-1, 0], // Up
[ 0, 1], // Right
[ 1, 0], // Down
[ 0,-1], // Left
];
Test Case
const assert = require('chai').assert;
describe('Number Of Islands', () => {
it('should return 1', () => {
const grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
];
const map = new NumberOfIslands(grid);
const result = map.getNumberOfIslands();
const expected = 1;
assert.strictEqual(result, expected);
});
it('should return 3', () => {
const grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
];
const map = new NumberOfIslands(grid);
const result = map.getNumberOfIslands();
const expected = 3;
assert.strictEqual(result, expected);
});
});
describe('Number Of Islands Union Find', () => {
it('should return 1', () => {
const grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
];
const map = new NumberOfIslandsUnionFind(grid);
const result = map.getNumberOfIslands();
const expected = 1;
assert.strictEqual(result, expected);
});
it('should return 3', () => {
const grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
];
const map = new NumberOfIslandsUnionFind(grid);
const result = map.getNumberOfIslands();
const expected = 3;
assert.strictEqual(result, expected);
});
});
Number Of Islands
✓ should return 1
✓ should return 3
Number Of Islands Union Find
✓ should return 1
✓ should return 3
4 passing (15ms)
