Interview Question
Share Lesson

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.

 

Breakdown

Loading...
Follow teacher
Share:

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...
Follow teacher
Share:

Table of Contents

Test Results

Run your code and see results 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.

 
 
// Upgrade for full course access
// Upgrade for full course access