PROBLEM
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.
REASONING
Suppose that we are given this grid:
grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
Let's draw a diagram of the grid:
The gray cells are land. I give them numbered labels to easily to make reference to in the explanation. In the code, they are referenced to by the row and column they are in. I defined a Cell interface for this particular purpose:
interface Cell {
row: number;
col: number;
}
My initial approach was, first, use an array to store all the land-cells, then use union-find algorithm to group all the neighboring cells together into 1 category, then count and return the number of category.
Let's sketch out the plan:
-
Create an array
cells, then go over all cells of the grid, when encounter a cell whose value is "1", add it tocells. The code should look like this:
const cells:Cell[] = []; for(let r = 0; r < grid.length; r++){ for(let c = 0; c < grid[r].length; c++){ if(grid[r][c] === "1") cells.push({ row: r, col: c }); } }
After step 1, the array cells should look like this:
- Create a union-find class that encompasses the union-find algorithm:
class UF {
private roots:number[];
private counts:number[];
private numCats:number;
constructor(size:length) {
this.roots = new Array(size).fill(0).map((o,i) => o + i);
this.counts = new Array(size).fill(1);
this.numCats = size;
}
union(i:number, j:number) {
const rootI = this.findRoot(i), rootJ = this.findRoot(j);
if(rootI === rootJ) return;
if(this.counts[rootI] > this.counts[rootJ]){
this.roots[rootJ] = rootI;
}
else {
this.roots[rootI] = rootJ;
}
const totalCounts = this.counts[rootI] + this.counts[rootJ];
this.counts[rootI] = totalCounts;
this.counts[rootJ] = totalCounts;
this.numCats--;
}
getNumCats():number {
return this.numCats;
}
private findRoot(i:number) {
if(this.roots[i] === i) return i;
this.roots[i] = this.findRoot(this.roots[i]);
return this.roots[i];
}
}
This is the typical way to implement a union-find class, so I won't spend too much time on that. If you want to learn more, you can read about it on leetcode or geeksforgeeks
-
For each element in the array
cells, pair them with each of all other elements in the arraycells. If they are neighbor, use union-find to group them into 1 category. The code should look like this:
const uF = new UF(); for(let i = 0; i < cells.length; i++){ for(let j = 0; j < cells.length - 1; j++){ if(//cells[i] and cells[j] are neighbors){ uF.union(i,j); } } }
Now, all the cells in cells are grouped into categories like this:
Our remained job now is just return the number of categories.
However, for this problem, I made a small modification. I moved the array cells to the union-find class then add a new method add to the class.
class UF {
private cells:Cell[];
// the rest of the variables
add(cell:Cell) {}
// the rest of the class
}
What add does is to get a cell, put it into the array cells, then go over all of the cells that are already in cells to check if each of them should be in the same category with the new cell. If it is, union them together. So, the function add should look like this:
add(cell:Cell) {
// push cell to cells
this.cells.push(cell);
// now we have 1 more new category, which is the one that has only 1 newly added cell.
this.numCats++;
// ... and this new category only has 1 element, which is the newly added cell
this.counts.push(1);
// ... the root of this category is its only element.
this.roots.push(this.roots.length);
// get the index of the new cell on the array cells
const newCellI = this.cells.length - 1;
// go over each element that is already in the array cells
for(let i = 0; i < newCellI; i++) {
if(// this.cells[newCellI] and this.cells[i] should be in the same category) {
// union them!
this.union(newCellI, i);
}
}
}
Notice the condition inside the for loop:
for(let i = 0; i < newCellI; i++) {
if(// this.cells[newCellI] and this.cells[i] should be in the same category) {
// union them!
this.union(newCellI, i);
}
}
To check if this.cells[newCellI] and this.cells[i] should be in the same category, we need to know if they are neighboring each other. To check if they're neighboring each other, we need to know their coordinates in the grid, the information that is not available in the UF class. So, why don't we just delegate the checking to the main function, which is the place where the coordinates information available?
We can do that by define the checking function inside the main function numIslands:
function numIslands(grid: string[][]): number {
const isNeighbors = (cell1: Cell, cell2:Cell):boolean => {
const {row:iRow, col:iCol} = cell1;
const {row:jRow, col:jCol} = cell2;
if((iCol === jCol && Math.abs(iRow - jRow) === 1)
|| (iRow === jRow && Math.abs(iCol - jCol) === 1)){
return true;
}
return false;
}
// the rest of the function
};
Then, when we instantiate the union-find class, we pass the isNeighbors function to its constructor:
const uF = new UF(isNeighbors);
Then, in the UF's constructor, we assign it to the private checking method:
class UF {
private roots:number[] = [];
private counts:number[] = [];
private numCats:number = 0;
private cells:Cell[] = [];
private shouldUnion: (c1:Cell, c2:Cell) => boolean;
constructor(shouldUnion:(c1:Cell, c2:Cell) => boolean) {
this.shouldUnion = shouldUnion;
}
// ... the rest of the class
}
Notice that we don't need to set up roots, counts, numCats inside the constructor anymore because at the beginning, we have 0 element. We will add them one by one and update those accordingly inside the function add.
So, my final code looks like this:
interface Cell {
row: number;
col: number;
}
function numIslands(grid: string[][]): number {
const isNeighbors = (cell1: Cell, cell2: Cell): boolean => {
const { row: iRow, col: iCol } = cell1;
const { row: jRow, col: jCol } = cell2;
if ((iCol === jCol && Math.abs(iRow - jRow) === 1) || (iRow === jRow && Math.abs(iCol - jCol) === 1))
return true;
return false;
}
const uF = new UF(isNeighbors);
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[r].length; c++) {
if (grid[r][c] === "1")
uF.add({
row: r,
col: c
});
}
}
return uF.getNumCats();
};
class UF {
private roots: number[] = [];
private counts: number[] = [];
private numCats: number = 0;
private cells: Cell[] = [];
private shouldUnion: (c1: Cell, c2: Cell) => boolean;
constructor(shouldUnion: (c1: Cell, c2: Cell) => boolean) {
this.shouldUnion = shouldUnion;
}
add(cell: Cell) {
this.cells.push(cell);
this.numCats++;
this.counts.push(1);
this.roots.push(this.roots.length);
const newCellI = this.cells.length - 1;
for (let i = 0; i < newCellI; i++) {
if (this.shouldUnion(this.cells[newCellI], this.cells[i])) {
this.union(newCellI, i);
}
}
}
union(i: number, j: number) {
const rootI = this.findRoot(i), rootJ = this.findRoot(j);
if (rootI === rootJ) return;
if (this.counts[rootI] > this.counts[rootJ]) {
this.roots[rootJ] = rootI;
}
else {
this.roots[rootI] = rootJ;
}
const totalCounts = this.counts[rootI] + this.counts[rootJ];
this.counts[rootI] = totalCounts;
this.counts[rootJ] = totalCounts;
this.numCats--;
}
getNumCats(): number {
return this.numCats;
}
private findRoot(i: number) {
if (this.roots[i] === i) return i;
this.roots[i] = this.findRoot(this.roots[i]);
return this.roots[i];
}
}
All is fine, right?
Unfortunately, it passed all but 1 test, where the time limit was exceeded. The one test that it fails has a humongous input like this:
What happened? What made it take too long?
Let's examine the add function:
add(cell: Cell) {
this.cells.push(cell);
this.numCats++;
this.counts.push(1);
this.roots.push(this.roots.length);
const newCellI = this.cells.length - 1;
for (let i = 0; i < newCellI; i++) {
if (this.shouldUnion(this.cells[newCellI], this.cells[i])) {
this.union(newCellI, i);
}
}
}
Notice the for loop? Basically, for every new cell that is being added to cells, you need to check if it is the neighbor of each of all cells that are already in cells. It is unnecessary to check all of them because we already know which ones among them are neighbors to the new cell: the one right below, right above, next to the left, and next to the right of it.
So, we can modify this for loop to make it faster. Instead of checking if each of all cells that are already in cells is the new cell's neighbor, we do the opposite, which is check if any of the new cell's neighbors is in cells. If there is such a cell, union the new cell to its group.
The for loop becomes like this:
// go over 4 directions: up, down, left, right
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dr, dc] of directions) {
// for each direction, get the neighbor cell in that direction.
const neighborCell:Cell = {row: row + dr, col: col + dc};
if(//the neighborCell is not a valid cell)
continue;
if (// the neighborCell is in the array cells) {
this.union(index, neighborIndex);
}
}
In the first if conditional, we need to check if neighborCell is not a valid cell. It is not a valid cell if its row is less than 0 or greater or equal to the grid's row size or its col is less than 0 or greater or equal to the grid's col size. In particular, this is how it looks like in code:
if(neighborCell.row < 0 || neighborCell.row >= this.gridRowSize
|| neighborCell.col < 0 || neighborCell.col >= this.gridColSize) {
continue;
}
Notice this.gridRowSize and this.gridColSize? Remember to give those information to the constructor when instantiate the class.
In the second if conditional, we need to check if neighborCell is in the array cells. This is tricky, because in union-find, we "encode" the identity of a node by its index in an array. For example, the array roots stores the root value of a node, right? So, the root value of the node that identity is 1 will be stored at index 1 in the array roots. So, the only piece of information that we can use to identify neighborCell in cells is its index in cells. But, to identify neighborCell, we need two pieces of information, which are its row and its column. How can we combine 2 pieces into 1 piece of information? Well, we can "flatten" the grid to make a 2D coordinate into only 1D coordinate. So, the index of neighborCellin a 1D array is const neighborIndex = neighborCell.row * this.gridColSize + neighborCell.col;
To check if it is in cells, we check if this.cells[neighborIndex] is undefined. Then, the second if conditional would look like this:
if (this.cells[neighborIndex] !== undefined) {
this.union(index, neighborIndex);
}
When come to think about it, we don't even need the array cells. In the previous implementation, we need it to store the coordinate of the land cells for the function shouldUnion to check. Now, we don't need shouldUnion, we can also eliminate the array cells.
The final code looks like this:
interface Cell {
row: number;
col: number;
}
class UF {
private roots: number[];
private counts: number[];
private numCats: number;
private gridRowSize: number;
private gridColSize: number;
constructor(rowSize: number, colSize: number) {
this.gridRowSize = rowSize;
this.gridColSize = colSize;
this.roots = [];
this.counts = [];
this.numCats = 0;
}
add(cell: Cell) {
const { row, col } = cell;
const index = row * this.gridColSize + col; // Calculate a unique index for each cell
this.roots[index] = index;
this.counts[index] = 1;
this.numCats++;
// Check four neighboring cells
const directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];
for (const [dr, dc] of directions) {
const neighborCell:Cell = {row: row + dr, col: col + dc};
if(neighborCell.row < 0 || neighborCell.row >= this.gridRowSize
|| neighborCell.col < 0 || neighborCell.col >= this.gridColSize) {
continue;
}
const neighborIndex = neighborCell.row * this.gridColSize + neighborCell.col;
if (this.roots[neighborIndex] !== undefined) {
this.union(index, neighborIndex);
}
}
}
union(i: number, j: number) {
const rootI = this.findRoot(i);
const rootJ = this.findRoot(j);
if (rootI === rootJ) return;
if (this.counts[rootI] > this.counts[rootJ]) {
this.roots[rootJ] = rootI;
this.counts[rootI] += this.counts[rootJ];
} else {
this.roots[rootI] = rootJ;
this.counts[rootJ] += this.counts[rootI];
}
this.numCats--;
}
getNumCats(): number {
return this.numCats;
}
private findRoot(i: number): number {
if (this.roots[i] === i) return i;
this.roots[i] = this.findRoot(this.roots[i]);
return this.roots[i];
}
}
function numIslands(grid: string[][]): number {
const numRows = grid.length;
const numCols = grid[0].length;
const uf = new UF(numRows, numCols);
for (let r = 0; r < numRows; r++) {
for (let c = 0; c < numCols; c++) {
if (grid[r][c] === '1') {
uf.add({ row: r, col: c });
}
}
}
return uf.getNumCats();
}
It beats 39.50% of users with TypeScript. Not ideal, but also not bad, consider that I came up to the solution all by myself.
Top comments (0)