Number Of Islands Solution for Accenture

Company: Accenture · Difficulty: Medium · Topics: Array, Depth-First Search, Breadth-First Search, Union Find

Problem Statement

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.

Key Understanding:

An island is a group of connected '1's (land cells)
Two cells are connected if they are adjacent horizontally or vertically (not diagonally)
We need to count the number of distinct connected components of '1's
The grid boundaries are surrounded by water

Examples

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

Explanation:

There is one large island in the top-left area
All '1's are connected to each other
Visual representation:

```

1 1 1 1 0

1 1 0 1 0

1 1 0 0 0

0 0 0 0 0

```

This forms 1 island.

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

Explanation:

There are three separate islands
Visual representation:

```

1 1 0 0 0

0 0 1 0 0

0 0 0 1 1

```

Island 1: Top-left 2x2 area
Island 2: Center single cell
Island 3: Bottom-right 2x1 area

Example 3:

Input: grid = [["1","0","1"],["0","1","0"],["1","0","1"]]

Output: 5

Explanation:

Each '1' forms its own island
No '1's are adjacent to each other
Visual representation:

```

1 0 1

0 1 0

1 0 1

```

This forms 5 separate islands.

Intuition

The key insight is to use a graph traversal algorithm (DFS or BFS) to explore connected components. When we find a '1', we mark it as visited and explore all its adjacent '1's recursively.

Graph Representation:

Each '1' cell is a node
Adjacent '1' cells are connected by edges
We need to count the number of connected components

Why DFS/BFS Works:

DFS/BFS will visit all connected '1's starting from any '1'
Each time we start a new DFS/BFS from an unvisited '1', we've found a new island
We can mark visited cells to avoid counting the same island multiple times

Approach

Approach 1: Depth-First Search (DFS)

Algorithm:

1. Iterate through each cell in the grid

2. When we find a '1' (unvisited land):

Increment island count
Start DFS from this cell to mark all connected '1's as visited

3. Return the total island count

DFS Function:

Mark current cell as visited (change '1' to '0' or use visited array)
Recursively call DFS on all four adjacent cells (up, down, left, right)
Base case: if cell is out of bounds or is '0'

Approach 2: Breadth-First Search (BFS)

Algorithm:

1. Same as DFS, but use a queue instead of recursion

2. When we find a '1':

Increment island count
Add current cell to queue
While queue is not empty:
Dequeue a cell
Mark it as visited
Add all adjacent '1's to queue

Approach 3: Union Find (Disjoint Set)

Algorithm:

1. Initialize Union Find with all '1' cells

2. For each '1' cell, union it with its adjacent '1' cells

3. Count the number of distinct roots (islands)

Dry Run

Let's trace through Example 2: grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]

DFS Approach:

Start at (0,0): found '1', island count = 1
DFS from (0,0): mark (0,0), (0,1), (1,0), (1,1) as visited
Continue scanning: (0,2), (0,3), (0,4) are '0'
(1,2), (1,3), (1,4) are '0'
(2,0), (2,1) are '0'
(2,2): found '1', island count = 2
DFS from (2,2): mark (2,2) as visited
(2,3), (2,4) are '0'
(3,0), (3,1), (3,2) are '0'
(3,3): found '1', island count = 3
DFS from (3,3): mark (3,3), (3,4) as visited

Result: 3 islands

Key Insights

1. Connected Components: This is essentially finding connected components in a graph

2. Visited Marking: Mark visited cells to avoid infinite loops and double counting

3. Boundary Conditions: Check array bounds before accessing adjacent cells

4. Adjacency: Only horizontal and vertical adjacency counts, not diagonal

5. In-Place Modification: Can modify the grid in-place to mark visited cells

Edge Cases

1. Empty Grid: Return 0

2. Single Cell: Grid with only one '1' cell

3. No Islands: Grid with only '0's

4. All Islands: Grid with only '1's (one large island)

5. Large Grid: Handle efficiently with proper algorithm choice

Solution

⚠️ Disclaimer: Don't jump directly to the solution, try it out yourself first. Only look at the solution after you've given it a good attempt.

Solution 1: DFS (Optimal)

Time Complexity: O(m*n) - We visit each cell at most once

Space Complexity: O(m*n) - In worst case, recursion stack can be m*n deep

Solution 2: BFS

Time Complexity: O(m*n) - We visit each cell at most once

Space Complexity: O(min(m,n)) - Queue size is bounded by the smaller dimension

Solution 3: Union Find

Time Complexity: O(m*n * α(m*n)) - α is the inverse Ackermann function

Space Complexity: O(m*n) - Space for Union Find data structure