Solution: Number of Islands

Let's solve the Number of Islands problem using the Union Find pattern.

We'll cover the following

Statement

Let’s consider a scenario with an (m×n)(m \times n) 2D grid containing binary numbers, where '0' represents water and '1' represents land. If any '1' cells are connected to each other horizontally or vertically (not diagonally), they form an island. Your task is to return the total number of islands in the grid.

Constraints:

  • 1≤1 \leq grid.length ≤300\leq 300

  • 1≤1 \leq grid[i].length ≤300\leq 300

  • grid[i][j] is either '0' or '1'.

Solution

The key approach is to traverse the 2D grid and join adjacent cell 1s horizontally or vertically. In the end, we return the number of connected components.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.