Max Area of Island
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
Return the area (number of cells) of the largest island in a grid of 1s and 0s, or 0 if there is none.
3Hint ladder
Take one rung at a time. Stop as soon as the idea clicks.
- Hint 1What does the flood function know when it finishes: how many cells did it sink?
- Hint 2Keep the maximum of those sizes.
4The approach
Have you tried the hints? The approach is built as a path from the obvious way to the clever one.
The spilled-tea stains again, but now you want the BIGGEST stain. When you start wiping a new stain, count every wet spot you wipe. When it is dry, compare that count with the largest stain so far.
- The obvious way
Same cost as the optimal flood; no cheaper way exists.
- The key insight
Scan the cells. At a land cell, flood it with a stack and count how many cells you sink. Update the best area with that count. Water or sunk cells are skipped.
- The algorithm
- best = 0. Scan all cells.
- At land: size = 0; flood, size + 1 per cell.
- best = max(best, size).
- Return best.
Watch it run
Examplegrid rows: 0110 / 0100 / 1001
Land at the top: flood it and count. It spreads to its right neighbour and the cell below: 3 cells.
best = 3
Where people slip
- Start best at 0 so a grid with no land returns 0.
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 max_area_of_island(grid):
rows, columns = len(grid), len(grid[0])
best = 0
for row in range(rows):
for column in range(columns):
if grid[row][column] != 1:
continue
grid[row][column] = 0 # sink it
area = 0
to_wipe = [(row, column)]
while to_wipe:
r, c = to_wipe.pop()
area += 1 # count every wet spot we wipe
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))
best = max(best, area)
return bestNow 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.