Data Structures & Algorithms › Graphs — BFS & DFS
💡
Exercise 109

Number of Islands 20 XP Medium

LeetCode Ctrl+Enter Run Ctrl+S Save

This is LeetCode #200: Number of Islands — the most classic graph problem and a top interview question! 🏝️

💡 Think of it like this: You're looking at a map from above. There's land ("1") and water ("0"). An island is a group of land cells that are connected up/down/left/right. How many separate islands do you see?

# Example: grid = [ ['1','1','0','0','0'], ['1','1','0','0','0'], ['0','0','1','0','0'], ['0','0','0','1','1'] ] # Answer: 3 islands! # Island 1: top-left (4 connected 1s) # Island 2: middle (1 alone) # Island 3: bottom-right (2 connected 1s)

The Algorithm — DFS (Depth-First Search):

  • 1️⃣ Scan the grid cell by cell
  • 2️⃣ When you find a '1' → it's the start of a NEW island! Count it.
  • 3️⃣ Use DFS to visit ALL connected land cells (up, down, left, right)
  • 4️⃣ Mark each visited cell as '0' (or '#') so we don't count it again
  • 5️⃣ Continue scanning. Each new '1' we find = another island.

💭 Time to code! Use the step-by-step approach described above. Don't peek at the solution — try first! 🚀

Complexity: Time O(rows × cols) — visit every cell once. Space O(rows × cols) — recursion stack in worst case.

📋 Instructions
Count the number of islands in the given grid using DFS flood-fill.
DFS! Scan the grid. When you find a '1', increment count and use DFS to mark ALL connected '1's as visited (change to '0'). Each DFS call explores one complete island.
⚠️ Try solving it yourself first — you'll learn more!
def numIslands(grid):
    count = 0
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c] == '1':     # Found new island!
                count += 1
                dfs(grid, r, c)       # Sink the whole island
    return count

def dfs(grid, r, c):
    # Out of bounds or water? Stop.
    if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != '1':
        return
    grid[r][c] = '0'       # Mark as visited (sink it)
    dfs(grid, r+1, c)      # Down
    dfs(grid, r-1, c)      # Up
    dfs(grid, r, c+1)      # Right
    dfs(grid, r, c-1)      # Left
🧪 Test Cases
Input
numIslands(grid)
Expected
3
Test case 1
← Previous Next Exercise →
main.py
Hi! I'm Rex 👋
Output
Ready. Press ▶ Run or Ctrl+Enter.
›