island

island.go

func largestIsland(grid [][]int) int {
    n:=len(grid)
    if n==0{
        return 0
    }
    visited:=make([][]bool,n)
    for i:=0; i<n; i++ {
        visited[i]=make([]bool,n)
    }
    islandArea:=make(map[int]int)
    coloring:=2
    for i:=0; i<n; i++{
        for j:=0;j<n; j++{
           if grid[i][j]==1{
                count:=DFS(&grid,visited,i,j,n,coloring)
                islandArea[coloring]=count
                coloring++
            }
        }
    } 
    res:=islandArea[2]
    for i:=0; i<n; i++{
        for j:=0;j<n; j++{
            if grid[i][j]==0{
               connectedIsland:=make(map[int]int) // check connected island from this 0 only once.
                if i-1>=0{
                    if grid[i-1][j]>1{
                        connectedIsland[grid[i-1][j]]=islandArea[grid[i-1][j]]
                    }
                }
                if i+1<n {
                    if grid[i+1][j]>1{
                        connectedIsland[grid[i+1][j]]=islandArea[grid[i+1][j]]
                    }
                }
                if j-1>=0{
                     if grid[i][j-1]>1{
                        connectedIsland[grid[i][j-1]]=islandArea[grid[i][j-1]]
                    }
                }
                if j+1<n{
                      if grid[i][j+1]>1{
                        connectedIsland[grid[i][j+1]]=islandArea[grid[i][j+1]]
                    }
                }
                maxCount:=1
                for _,count:=range connectedIsland{
                    maxCount+=count
                }
                if maxCount>res{
                    res=maxCount
                }
           }
        }
    }
    return res
}

func DFS (grid *[][]int, visited [][]bool, row,col,n,color int) int{
    if visited[row][col]{
        return 0
    }
    count:=0
    (*grid)[row][col]=color
    visited[row][col]=true
    if row-1>=0 && !visited[row-1][col]&& (*grid)[row-1][col]==1{
        count+=DFS(grid,visited,row-1,col,n,color)
    }
    if row+1<n && !visited[row+1][col]&& (*grid)[row+1][col]==1{
       count+= DFS(grid,visited,row+1,col,n,color)
    }
    if col-1>=0 && !visited[row][col-1]&& (*grid)[row][col-1]==1{
       count+= DFS(grid,visited,row,col-1,n,color)
    }
    if col+1<n && !visited[row][col+1]&& (*grid)[row][col+1]==1{
        count+=DFS(grid,visited,row,col+1,n,color)
    }
    return count+1
}