Number of Islands

Medium

Python

def num_islands(grid):
    count=0
    def dfs(r,c):
        if r<0 or r>=len(grid) or c<0 or c>=len(grid[0]) or grid[r][c]!='1': return
        grid[r][c]='0'
        dfs(r+1,c);dfs(r-1,c);dfs(r,c+1);dfs(r,c-1)
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c]=='1': count+=1; dfs(r,c)
    return count

Java

public int numIslands(char[][] grid){
    int count=0;
    for(int r=0;r<grid.length;r++)
        for(int c=0;c<grid[0].length;c++)
            if(grid[r][c]=='1'){count++;dfs(grid,r,c);}
    return count;
}
void dfs(char[][] g,int r,int c){
    if(r<0||r>=g.length||c<0||c>=g[0].length||g[r][c]!='1') return;
    g[r][c]='0';
    dfs(g,r+1,c);dfs(g,r-1,c);dfs(g,r,c+1);dfs(g,r,c-1);
}

Key Insight

Python nested function captures grid. Java passes explicitly. DFS identical.

Python → Java Differences

Nested function captures grid
Java passes grid as param
4-direction DFS identical

Python

def num_islands(grid):
    count=0
    def dfs(r,c):
        if r<0 or r>=len(grid) or c<0 or c>=len(grid[0]) or grid[r][c]!='1': return
        grid[r][c]='0'
        dfs(r+1,c);dfs(r-1,c);dfs(r,c+1);dfs(r,c-1)
    for r in range(len(grid)):
        for c in range(len(grid[0])):
            if grid[r][c]=='1': count+=1; dfs(r,c)
    return count

Java

public int numIslands(char[][] grid){
    int count=0;
    for(int r=0;r<grid.length;r++)
        for(int c=0;c<grid[0].length;c++)
            if(grid[r][c]=='1'){count++;dfs(grid,r,c);}
    return count;
}
void dfs(char[][] g,int r,int c){
    if(r<0||r>=g.length||c<0||c>=g[0].length||g[r][c]!='1') return;
    g[r][c]='0';
    dfs(g,r+1,c);dfs(g,r-1,c);dfs(g,r,c+1);dfs(g,r,c-1);
}

Algorithm Steps

1. For each unvisited land:
2. Count and DFS to mark

All Graphs Next →