Python solution with explaination, 372 ms, 100% for now.


  • 0
    C

    In a DP way, we add one land after another. For each addLand, naturally, we will check the 4 neighbors. If all 4 are water, then we have a new island; if only 1 is land, then we simply add the new patch of land to that island; if 2 or 3 or 4 are land, we need to know how many islands are involved, then we merge all the islands, and add the new land to the merged island as well. When we merge, we merge smaller islands to the largest one, to curb the worst case time in control.

    To implement this thought, we will need a table to to translate positions to islands, and we will also need to know the territory of a given island. This way, we will be able to immediately find out how many islands are neighboring the new land, and find out which lands are involved in the merging.

    So, we have "islands" to list all islands, and each island is a list of land inside it. We also have a table pos2island to record which island a specific position belongs to: pos2island[x][y]=(index in islands). I use index instead of the actual list here because index is hashable.

    The code that follows should be pretty self-explanatory:

    class Solution(object):
    def numIslands2(self, m, n, positions):
        """
        :type m: int
        :type n: int
        :type positions: List[List[int]]
        :rtype: List[int]
        """
        #set to 0 to simplify code with the [-1] operation
        result=[0]
    
        islands=[]
    
        pos2island=[[-1]*n for _ in xrange(m)]
    
        for p in positions:
            #find out how many islands are neighboring the new land
            neighborIslandsIndexes=set()
            if p[0]!=0 and pos2island[p[0]-1][p[1]] >=0 :
                neighborIslandsIndexes.add(pos2island[p[0]-1][p[1]])
            if p[0]!=m-1 and pos2island[p[0]+1][p[1]] >=0:
                neighborIslandsIndexes.add(pos2island[p[0]+1][p[1]])
            if p[1]!=0 and pos2island[p[0]][p[1]-1] >=0 :
                neighborIslandsIndexes.add(pos2island[p[0]][p[1]-1])
            if p[1]!=n-1 and pos2island[p[0]][p[1]+1] >=0:
                neighborIslandsIndexes.add(pos2island[p[0]][p[1]+1])
    
            result.append(result[-1]+1-len(neighborIslandsIndexes))
    
            #case 0 is simple
            if len(neighborIslandsIndexes)==0:
                islands.append([p])
                pos2island[p[0]][p[1]]=len(islands)-1
            #case 1,2,3,4, we may need to merge multiple islands
            else:
                #find out which island is largest
                largestNeighborIsland_Index=-1
                largestNeighborIslandSize=0
                for i in neighborIslandsIndexes:
                    if len(islands[i])>largestNeighborIslandSize:
                        largestNeighborIsland_Index=i
                        largestNeighborIslandSize=len(islands[i])
    
                #add the new land to the largest island
                pos2island[p[0]][p[1]]=largestNeighborIsland_Index
                islands[largestNeighborIsland_Index].append(p)
    
                #add the lands of all other neighboring islands to the largest one
                neighborIslandsIndexes.remove(largestNeighborIsland_Index)
                for i in neighborIslandsIndexes:
                    for l in islands[i]:
                        pos2island[l[0]][l[1]]=largestNeighborIsland_Index
                    islands[largestNeighborIsland_Index].extend(islands[i])
    
        return result[1:]

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.