Landlocked Islands
Problem
A map is a grid of 1s for land and 0s for water, and an island is a group of land cells joined up, down, left or right. Count the islands that are completely surrounded by water inside the map, meaning no cell of the island lies in the first or last row or column. Islands that touch the edge might continue off the map, so they do not count. The grid may be empty.
Examples
Input: grid = [[1, 1, 0, 0, 0],
[1, 0, 0, 1, 0],
[0, 0, 1, 1, 0],
[0, 0, 0, 0, 0],
[0, 1, 0, 0, 1]]
Output: 1
Why: only the three cells in the middle stay clear of the edgeInput: grid = [[0, 0, 0],
[0, 1, 0],
[0, 0, 0]]
Output: 1
Why: a single inland cell is an islandInput: grid = [[1]]
Output: 0
Why: edge case, the only cell lies on the edgeHints
0 / 3
Counting islands is a flood fill per unvisited land cell. The only new question is how to tell whether an island touches the edge.
While you walk an island, every cell you visit can report whether it sits in the first or last row or column.
For each unvisited land cell, explore its whole island with a stack, marking cells as seen. Keep one flag per island that turns false as soon as any cell is on the border, and add one to the count only when the flag survives.
Solution
Every island is explored once with a stack-based flood fill that starts at its first unvisited cell and marks cells as seen so none is walked twice. During that walk a single flag records whether any cell lies on the border, which is all that decides if the island counts. An iterative stack avoids deep recursion on large islands. Time is O(rows times cols) because each cell is visited a constant number of times, and space is O(rows times cols) for the seen set.
def landlocked_islands(grid):
rows, cols = len(grid), len(grid[0]) if grid else 0
seen, count = set(), 0
for r0 in range(rows):
for c0 in range(cols):
if grid[r0][c0] != 1 or (r0, c0) in seen: continue
seen.add((r0, c0))
stack, inland = [(r0, c0)], True
while stack: # walk one whole island
r, c = stack.pop()
if r in (0, rows - 1) or c in (0, cols - 1): inland = False
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 1 and (nr, nc) not in seen:
seen.add((nr, nc)); stack.append((nr, nc))
count += inland
return count
print(landlocked_islands([[1, 1, 0, 0, 0], [1, 0, 0, 1, 0], [0, 0, 1, 1, 0], [0, 0, 0, 0, 0], [0, 1, 0, 0, 1]])) # -> 1
print(landlocked_islands([[0, 0, 0], [0, 1, 0], [0, 0, 0]])) # -> 1
print(landlocked_islands([[1]])) # -> 0Stuck on the idea rather than the code? Number of Islands covers it.