Finding Islands In a Binary Matrix

There is a problem that very often tends to pop up in a lot of technical coding interviews because the solution can be trivial if the candidate understands core concepts of computer science such as recursion and depth first search. It also reveals in-depth knowledge of graphs and common graph traversal algorithms. The problem statement is, given an NxN matrix which contains only 0's and 1's find the number of islands within the matrix. An island is defined as adjacent matrix cells containing 1's, where adjacent means horizontal, vertical and diagonal neighbor cells. In this article I present an efficient enough algorithm with O(n) complexity that takes advantage of a depth first search approach to quickly iterate through the matrix and recursively detect islands.

Read More