This problem follows the Grid DFS/BFS pattern, commonly found in the Graphs category. Recognizing this pattern is key to solving it efficiently in an interview setting.
For each unvisited '1', run DFS/BFS to mark all connected land. Increment count.
Mutating the grid to mark visited cells avoids a separate visited set — each cell is visited at most once, giving O(m*n) total.
count = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
count += 1
dfs(i, j) # marks all connected land as '0'
def dfs(i, j):
if i<0 or j<0 or i>=rows or j>=cols or grid[i][j]=='0':
return
grid[i][j] = '0'
dfs(i+1,j); dfs(i-1,j); dfs(i,j+1); dfs(i,j-1)
return countPractice Number of Islands and similar Graphs problems with flashcards. Build pattern recognition through active recall.
Practice this problem