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
Approach and test strategy
Four-neighbor flood fill with explicit land and water markers
Read the approach, boundary cases, and complexity
The course grid represents land with # and water with ~. Scan cells and start a traversal whenever an unvisited land cell is found. That traversal marks its whole four-neighbor component, so the outer scan counts it once. Diagonal contact alone does not connect islands. Mark discovery before adding a neighbor to the frontier to avoid repeating the same work through several incoming paths.
Cases to check
- Test an empty row, one water cell, and one land cell.
- Separate land cells diagonally to check the four-neighbor rule.
- Use a long narrow island and decide whether the implementation preserves or deliberately marks the input.
Cost model
For r rows and c columns, the scan and flood fills take O(r · c) time. A visited set or an explicit traversal frontier can require O(r · c) auxiliary storage in the worst case.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
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.