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
Validate My Answer
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.
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.
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.