Prompt: Given an m x n 2D array that represents a map. Each value has either “1” or “0” where it represents land or water, respectively.

Goal: Find how many islands there are.

Note: An island is all adjacently vertically or horizontally connected lands.

Examples:

1 0 1 
0 1 0 
1 0 1

There are 5 islands.

1 1 1
0 0 0 
1 0 0 

There are 2 islands

1 0 1
1 1 1 
1 0 1

There is 1 island.

1 0 1
1 1 0 
1 0 1

There are 3 islands.

Solution: One island can be represented by one piece of the land. Then, we can just invalidate all other pieces of the island to avoid recounting the same island. This is a search problem to search and invalidate all other pieces of the same island when there is an island founded.

Example:

1 1 1
0 0 0 
1 0 0 

1 island is found in indices (0,0) 
We need to invalidate all its other pieces

1 x x
0 0 0 
1 0 0 

We can use DFS to search for all other pieces of the first island. Then, we can invalidate the pieces by replacing the 1's with x's

1 x x
0 0 0 
1 0 0

2 islands are found