package com.tolchev.algo.matrix

class NumberOfIslands {
    private val DEFAULT_ISLAND = -1
    fun numIslands(grid: Array<CharArray>): Int {
        var islands = Array<IntArray>(grid.size){ IntArray(grid[0].size){DEFAULT_ISLAND} }

        var topIsland :  Int
        var leftIsland :  Int

        var islandCount = 0

        var groups = LinkedHashMap<Int, Int>()

        for (row in grid.indices){
            for (col in grid[0].indices){
                if (grid[row][col] == '0'){
                    continue
                }

                topIsland = if (row ==0) DEFAULT_ISLAND else islands[row-1][col]
                leftIsland = if (col ==0) DEFAULT_ISLAND else islands[row][col-1]

                if (topIsland == DEFAULT_ISLAND && leftIsland == DEFAULT_ISLAND){
                    islands[row][col] = islandCount
                    groups[islandCount] = islandCount
                    islandCount++
                }
                else if (topIsland == DEFAULT_ISLAND && leftIsland != DEFAULT_ISLAND){
                    islands[row][col] = leftIsland
                }
                else if (leftIsland == DEFAULT_ISLAND &&  topIsland!= DEFAULT_ISLAND){
                    islands[row][col] = topIsland
                }
                else{
                    if (leftIsland != topIsland ){
                        val maxIsland = Math.max(leftIsland, topIsland)
                        val minGroup  = Math.min(groups[leftIsland]!!, groups[topIsland]!!)
                        islands[row][col] = minGroup
                        groups[maxIsland] = minGroup
                    }
                    else{
                        islands[row][col] = leftIsland
                    }
                }
            }
        }

        var correctGroups = arrayListOf<Int>()

        for (group in groups){
            var parentGroup = group.value

            while (parentGroup != groups[parentGroup]){
                parentGroup = groups[parentGroup]!!
            }

            correctGroups.add(parentGroup)
        }

        return correctGroups.distinct().size
    }
}

