0
$\begingroup$

This question already has an answer here:

I had this question in an interview recently. I was unable to answer this question and would really like to start a discussion on how to approach this problem and get the most efficient solution.

You have this matrix. You want to print out how many islands are in the matrix. Assume water is surrounding everything outside of the matrix.

An island is any land completely surrounded by water. Land pieces can be connected to form an island as well. As long there is another piece of land in any of the surrounding blocks, that piece of land is considered a part of that island, and yes this includes diagonals.

M = 'land'
o = 'water'

world = [
  [o,M,o,o,o,M,o,o,o,o,o],
  [o,o,M,o,M,M,o,o,o,o,o],
  [o,o,o,o,o,M,o,o,M,M,o],
  [o,o,o,M,o,M,o,o,o,M,o],
  [o,o,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,M,M,M,M,o,o,o],
  [M,M,M,M,M,M,M,M,M,M,M],
  [o,o,o,M,M,o,M,M,M,o,o],
  [o,o,o,o,o,o,M,M,o,o,o],
  [o,M,o,o,o,M,M,o,o,o,o],
  [o,o,o,o,o,M,o,o,o,o,o]]

In this example, there are 5 islands.

I attempted to answer this with for loops but was unable to do so as this seems more of a recursive problem. Unfortunately, I am not the most proficient with recursion and would really like to see the thought process you take to tackle this and the running time of your algorithm :).

Feel free to use your favorite programming language. Also If I didn't describe the problem clearly enough just leave a comment and I'll do my best to clarify.

$\endgroup$

marked as duplicate by D.W. algorithms May 7 '17 at 2:44

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ Coding questions are off-topic here. A very similar question was asked recently. Interesting how multiple people seem to be receiving the same problem at the same time. $\endgroup$ – D.W. May 7 '17 at 2:45
  • $\begingroup$ Thank you for pointing that out was not entirely sure where to post this one. $\endgroup$ – Konstantino Sparakis May 7 '17 at 3:07