200. Number of Islands

Medium

Problem Description

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Examples

Example 1:
Input: grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
Output: 1

Example 2:
Input: grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
Output: 3
Jump to Solution: Python Java C++ JavaScript C#

Python Solution


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        def dfs(i: int, j: int) -> None:
            if (i < 0 or i >= len(grid) or 
                j < 0 or j >= len(grid[0]) or
                grid[i][j] != '1'):
                return
            
            # Mark as visited
            grid[i][j] = '#'
            
            # Check all 4 directions
            dfs(i+1, j)
            dfs(i-1, j)
            dfs(i, j+1)
            dfs(i, j-1)
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    dfs(i, j)
                    count += 1
        
        return count

BFS Solution:


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        rows, cols = len(grid), len(grid[0])
        count = 0
        
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    count += 1
                    queue = deque([(i, j)])
                    grid[i][j] = '#'  # Mark as visited
                    
                    while queue:
                        row, col = queue.popleft()
                        directions = [(1,0), (-1,0), (0,1), (0,-1)]
                        
                        for dr, dc in directions:
                            r, c = row + dr, col + dc
                            if (0 <= r < rows and 0 <= c < cols and
                                grid[r][c] == '1'):
                                queue.append((r, c))
                                grid[r][c] = '#'
        
        return count

Java Solution


class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        
        int count = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || 
            j < 0 || j >= grid[0].length || 
            grid[i][j] != '1') {
            return;
        }
        
        // Mark as visited
        grid[i][j] = '#';
        
        // Check all 4 directions
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

C++ Solution


class Solution {
public:
    int numIslands(vector>& grid) {
        if (grid.empty()) {
            return 0;
        }
        
        int count = 0;
        for (int i = 0; i < grid.size(); i++) {
            for (int j = 0; j < grid[0].size(); j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
private:
    void dfs(vector>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || 
            j < 0 || j >= grid[0].size() || 
            grid[i][j] != '1') {
            return;
        }
        
        // Mark as visited
        grid[i][j] = '#';
        
        // Check all 4 directions
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
};

JavaScript Solution


/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    if (!grid.length) {
        return 0;
    }
    
    const dfs = (i, j) => {
        if (i < 0 || i >= grid.length ||
            j < 0 || j >= grid[0].length ||
            grid[i][j] !== '1') {
            return;
        }
        
        // Mark as visited
        grid[i][j] = '#';
        
        // Check all 4 directions
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    };
    
    let count = 0;
    for (let i = 0; i < grid.length; i++) {
        for (let j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === '1') {
                dfs(i, j);
                count++;
            }
        }
    }
    
    return count;
};

C# Solution


public class Solution {
    public int NumIslands(char[][] grid) {
        if (grid == null || grid.Length == 0) {
            return 0;
        }
        
        int count = 0;
        for (int i = 0; i < grid.Length; i++) {
            for (int j = 0; j < grid[0].Length; j++) {
                if (grid[i][j] == '1') {
                    DFS(grid, i, j);
                    count++;
                }
            }
        }
        return count;
    }
    
    private void DFS(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.Length || 
            j < 0 || j >= grid[0].Length || 
            grid[i][j] != '1') {
            return;
        }
        
        // Mark as visited
        grid[i][j] = '#';
        
        // Check all 4 directions
        DFS(grid, i + 1, j);
        DFS(grid, i - 1, j);
        DFS(grid, i, j + 1);
        DFS(grid, i, j - 1);
    }
}

Complexity Analysis

Solution Explanation

There are two main approaches to solve this problem:

Key Points

Common Pitfalls

Optimization