200. Number of Islands
Published: 2024-03-11 22:07:16

### 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:


![Grid diagram](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/i1q3svoc6flzkxvteq41.PNG)

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:

```typescript
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:

1. Create an array `cells`, then go over all cells of the grid, when encounter a cell whose value is "1", add it to `cells`. The code should look like this:
	
	```typescript
		 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:


![The cells array](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/0a4c5qoicwgbeqz0dl5a.PNG)

2. Create a union-find class that encompasses the union-find algorithm:

```typescript
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](https://leetcode.com/discuss/general-discussion/1072418/Disjoint-Set-Union-(DSU)Union-Find-A-Complete-Guide) or [geeksforgeeks](https://www.geeksforgeeks.org/introduction-to-disjoint-set-data-structure-or-union-find-algorithm/)

3. For each element in the array `cells`, pair them with each of all other elements in the array `cells`. If they are neighbor, use union-find to group them into 1 category. The code should look like this:
 
	```typescript
	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:


![The cells array after union-find](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/imm6suztl9y93fdqoyew.PNG)

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.

```typescript
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:

```typescript
 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:

```typescript
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`:

```typescript
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:

```typescript
    const uF = new UF(isNeighbors);
```

Then, in the UF's constructor, we assign it to the private checking method:

```typescript
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:

```typescript
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:


![Time limit exceeded result](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c5xulwoow0rn8mdbo58x.PNG)

What happened? What made it take too long?

Let's examine the `add` function:

```typescript
	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:

```typescript

// 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:

```typescript
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 `neighborCell`in 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:

```typescript
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:


```typescript
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.


![Final result](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ss153x5jw8c96sair6fu.PNG)