# Count Islands

## Course launching November 17, 2020

**Follow me on YouTube** for free coding interview videos.

Users who sign up for the email list will receive an exclusive 75% discount at launch.

**Write a function countIslands that takes an m x n matrix of characters and returns the number of islands.**

In our matrix, land is represented by the hashtag symbol `#`

and water is represented by the tilde `~`

.
Land is considered connected (and part of the same island) if `#`

directly touch horizontally or vertically.
If land touches diagonally, it is not considered connected.

You can ignore constraints around memory and should instead focus on solving the problem and writing good code. You can use DFS or BFS, and it can be done either iteratively or recursively.

```
// Example 1
~~~~~~####~~~~
~~~####~~~~~~~
~~~~~~~~~~####
~~~~~~~~~~~###
~~~~~~~~~~~###
Answer: 2
// Example 2
~~~##
~~~##
~#~~~
~~#~~
~~~~#
Answer: 4
```

### Validate My Answer

You will first need to find an island (linear matrix scan) and then once one is found, you perform a graph search to account for all its connected land pieces. Then you'll need to mark of all of its connected land as accounted for so you don't count this island more than once in the solution.

If you solve this recursively, don't forget your base case. Account for all the ways you reach the end of an island.

You need to visit every node, so the best time complexity you can achieve is

*O(m x n)*. If your time complexity is worse than this (after dropping constants), you can improve your solution.