Count Islands Coding Interview Question | Skilled.dev
Interview Question

Count Islands

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 # pieces 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. This means you can use DFS or BFS, and it can be done either iteratively or recursively.

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

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

Breakdown

Loading...

Table of Contents

Validate My Answer

  1. You will first need to find an island (linear matrix scan) and then once one is found, you traverse all of its connected land pieces. Then you'll track that each of the land pieces contained in this island have been used so they aren't double-counted.

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

  3. 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.

Loading...

Table of Contents

Test Results

Run your code and see results here...

const countIslands = (map) => {
  // Your solution here
};
// Upgrade for full course access
// Upgrade for full course access

Count Islands

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 # pieces 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. This means you can use DFS or BFS, and it can be done either iteratively or recursively.

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

// Example 2
~~~##
~~~##
~#~~~
~~#~~
~~~~#
Answer: 4
const countIslands = (map) => {
  // Your solution here
};
// Upgrade for full course access
// Upgrade for full course access