Archipelago Count
EasyGraphsFree
Problem
A survey drone photographs a stretch of sea and turns it into a map grid: a list of equal-length strings where # is land and . is water.
Two land cells belong to the same island when they touch horizontally or vertically (diagonal contact does not count). Return how many separate islands the map contains.
Example 1
- Input:
- grid = ["##..", "#..#", "..##"]
- Output:
- 2
The three land cells in the top-left corner form one island; (1,3), (2,2) and (2,3) form the other.
Example 2
- Input:
- grid = ["#.#", ".#.", "#.#"]
- Output:
- 5
The land cells only touch diagonally, so each one is its own island.
Constraints
- 1 ≤ rows, cols ≤ 300
- Every row has the same length.
- grid[r][c] is '#' or '.'
Hint
Show the first hint
Every island is a connected group of land cells. How do you visit a whole group starting from one of its cells?
Walkthrough
How to approach it
01Clarify before coding
- Do diagonal neighbours connect? No, only up, down, left and right.
- Can I modify the grid to mark visited cells? The rows are strings here, so keep a separate visited matrix (or ask; mutating input is often discouraged).
- Can the map have no land at all? Yes, then the answer is 0.
02Brute force
For each pair of land cells, decide whether they are connected by searching a path, then group them. Or repeatedly re-scan the grid merging neighbouring labels until nothing changes.
Cost: Pairwise path checks are O((rc)²) or worse; repeated label passes can take O(rc) passes of O(rc) each. Both are far too slow on a 300 × 300 map.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.