Islands in a grid are formed by connecting adjacent land cells (`L`

). We are tasked with finding the smallest island in a given grid. In this blog post, we’ll explore how to approach this problem using depth-first search (DFS), breaking it down step-by-step.

#### Problem Definition

We have a grid represented by a 2D array where:

**W**represents water.**L**represents land.

An island is a group of connected land cells (`L`

). Connected means horizontal or vertical adjacency, not diagonal. We need to find the minimum island size in the grid.

Here’s the grid:

```
const grid =
[ ['W', 'L', 'W', 'W', 'W'],
['W', 'L', 'W', 'W', 'W'],
['W', 'W', 'W', 'L', 'W'],
['W', 'W', 'L', 'L', 'W'],
['L', 'W', 'W', 'L', 'L'],
['L', 'L', 'W', 'W', 'W'],
];
```

### Approach

To solve this, we can use DFS to explore all land cells (`L`

) connected to a starting cell. We’ll iterate over each cell in the grid, and if it’s part of an island that hasn’t been visited yet, we will perform a DFS to calculate the size of that island. The minimum size encountered during this process will be our result.

### Steps

**Mark Cells as Visited**: As we traverse the grid, we need to track the cells we’ve already visited to avoid recounting the same island.**Depth-First Search (DFS)**: We’ll use DFS to explore all the adjacent cells that are part of the same island.**Track Minimum Island Size**: After exploring each island, update the minimum size if the current island is smaller than the previously recorded minimum.

Here’s the DFS-based solution:

```
const minimumIsland = (grid) => {
const visited = new Set();
let minSize = Infinity;
for (let r = 0; r < grid.length; r++) {
for (let c = 0; c < grid[0].length; c++) {
const size = exploreIsland(grid, r, c, visited);
if (size > 0 && size < minSize) {
minSize = size;
}
}
}
return minSize;
};
const exploreIsland = (grid, r, c, visited) => {
const rowInBounds = r >= 0 && r < grid.length;
const colInBounds = c >= 0 && c < grid[0].length;
if (!rowInBounds || !colInBounds || grid[r][c] === 'W') return 0;
const pos = r + ',' + c;
if (visited.has(pos)) return 0;
visited.add(pos);
let size = 1; // count the current land
size += exploreIsland(grid, r - 1, c, visited); // up
size += exploreIsland(grid, r + 1, c, visited); // down
size += exploreIsland(grid, r, c - 1, visited); // left
size += exploreIsland(grid, r, c + 1, visited); // right
return size;
};
console.log(minimumIsland(grid)); // -> 2
```

#### DFS Explained

- We start from a cell, check if it’s a land cell (
`L`

), and if so, mark it as visited. - We recursively explore its neighbors (up, down, left, right).
- As we explore, we count the number of land cells connected to form the current island.
- Once all connected cells have been visited, we compare the size of the island with the current minimum size and update if needed.