Number of Islands
1Try it yourself first
Think for 20-30 minutes before you open any hint. Being stuck is where the learning happens.
Only for you, saved in this browser. After you see the approach you will compare it with your idea.2What is being asked
Count the islands in a grid of '1' (land) and '0' (water). An island is land connected up, down, left or right.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1If you find one land cell, how do you make sure you do not count the rest of its island again?
- Hint 2Turn visited land into water (or keep a visited set) while flooding.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
Tea spilled on a tablecloth in several stains. To count the stains, scan the cloth. Each time you touch a wet spot you have not wiped yet, you say "a new stain", then wipe every connected wet spot of it dry, spreading outward. Next time you meet a wet spot it must belong to a different stain.
- The obvious way
Compare every pair of land cells for connection: very slow.
- The key insight
Scan every cell. At an unvisited land cell, add one to the count and flood: push it on a stack, mark it sunk ('0'), and repeatedly pop a cell and push its land neighbours after sinking them. Each cell is sunk once, so the work is O(rows x columns).
- The algorithm
- count = 0. Scan every cell.
- Land found: count + 1.
- Flood: sink it and keep spreading to all land neighbours.
- Return count.
Watch it run
Examplegrid rows: 1100 / 1001 / 0011
Scanning finds land at the top-left: island number 1. Flood its connected cells: the one to the right and the one below.
count = 1
Where people slip
- Mark a cell visited when you push it, not when you pop it, or it can be pushed many times.
- Diagonal cells are NOT connected here, only the four directions.
How close was your idea?
You did not write an idea, and that is fine.
Be honest with yourself. This sets your revision list.
5Code
Try writing it yourself from the steps first. Then compare.
def num_islands(grid):
rows, columns = len(grid), len(grid[0])
islands = 0
for row in range(rows):
for column in range(columns):
if grid[row][column] != "1":
continue
islands += 1 # a stain we have not wiped yet
grid[row][column] = "0" # sink it
to_wipe = [(row, column)]
while to_wipe:
r, c = to_wipe.pop()
for next_row, next_column in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= next_row < rows and 0 <= next_column < columns and grid[next_row][next_column] == "1":
grid[next_row][next_column] = "0"
to_wipe.append((next_row, next_column))
return islandsNow close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.
6Still stuck? Watch a video
Seeing someone explain it out loud can make it click. Try the video after you have read the approach above.