Python solution. Not very fast, but creative thought.


  • 0

    I didn't think about DFS or BFS when encountered this problem. I came up with this solution. The run time is O(n^2) average with n being the number of cells in the grid.

    I've learned a lot by reading other's solutions. My idea here may be interesting. Explanation is in the comments.

    class Solution(object):
        # Steps:
        # 1. Flood fill. Scan row by row.
        #    If cell value is 1, add cell coordinates to "Bag of lands"
        #    Check immediate sorroundings of the cell, see if they are already in bag of lands.
        #        If yes, do not increment island count. Add this land to that lsland's list of lands
        #        If no, increment island count by 1
        #        If this check is "yes" for two islands, we know they need to merge.
        # 3. Output result
        #
        # The bag of lslands will be a dictionary eventually of size at most 2n (n is number of cells).
        # It contains keys as labels of islands(1,2,3,4...), the value of such key is list of land
        # coordiantes. And it also contains keys as tuples as coordinates, the value of such key is
        # the island label.
        
        
        def checkLandAdjacency(self, cell, bag):
            # Check cells in adjacent 2 directions, left and up. Only need to check 2
            # because we assume we scan from top to down, from left to right. 
            #   Besides, We don't care grid dimensions here, since invalid cells won't
            # be in the bag anyways.
            i, j = cell
            
            labelLeft = -1
            labelUp = -1
            hasAdjacentLand = False
            hasDifferentAdjacentLand = False
            if (i, j-1) in bag:  # Left
                hasAdjacentLand = True
                labelLeft = bag[(i,j-1)]
                
            if (i-1, j) in bag:  # Up
                hasAdjacentLand = True
                labelUp = bag[(i-1, j)]
                if labelUp != -1 and labelLeft != -1 and labelUp != labelLeft:
                    # We encountered two different islands!
                    hasDifferentAdjacentLand = True
                    
            # Note that we prefer the cell in the leftwards direction, for consistency.
            return (hasAdjacentLand, hasDifferentAdjacentLand, labelLeft, labelUp)
        
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            if len(grid) == 0:
                return 0
    
            bag = {}
            maxLabel = 0  # The label of current island.
            for i in range(len(grid)):
                for j in range(len(grid[i])):
                    cell = grid[i][j]
                    if cell == "1":
                        hasAdjacentLand, hasDifferentAdjacentLand, labelLeft, labelUp \
                            = self.checkLandAdjacency((i,j), bag)
                        label = labelLeft if labelLeft >= 0 else labelUp
                        if hasAdjacentLand:
                            # Add this cell to the bag. Two keys
                            bag[(i,j)] = label
                            bag[label].append((i,j))
                        else:
                            # This might be a new island.
                            maxLabel += 1
                            bag[(i,j)] = maxLabel
                            bag[maxLabel] = [(i,j)]
                            
                        if hasDifferentAdjacentLand:
                            # Merge the two islands. Merge left to up.
                            landsLeft = bag[labelLeft]
                            for ll in landsLeft:
                                bag[ll] = labelUp
                                bag[labelUp].append(ll)
                            bag.pop(labelLeft)
                              
            count = 0  
            for key in bag:
                if type(key) is int:
                    count += 1
                    
            return count
    

  • 0

    What makes you say the run time is O(n^2) average? Isn't it simply O(n^2)?


  • 0

    Probably you're correct. I was thinking the "merge" step may require rescan of already-scanned cells which causes the runtime to be even slower. But this will not increase the exponential level of runtime. It's O(n^2)


  • 0

    What do you mean with rescan? You're just relabeling, right? So O(n) times you're relabeling O(n) cells.

    Would be better to relabel the smaller existing island, btw, instead of the left island. Right now a case like this will be expensive for you (I use # to mark islands for better visibility.

    #.#.#.#.#.#.#.#.#.#
    ###################
    #..................
    #.#.#.#.#.#.#.#.#.#
    ###################
    #..................
    #.#.#.#.#.#.#.#.#.#
    ###################
    #..................
    #.#.#.#.#.#.#.#.#.#
    ###################
    

  • 0

    Here's code generating a roughly 100×100 grid of the above kind. Your solution takes almost one second for it:

            n = 100
            grid = []
            for _ in range(n / 3):
                grid += '10' * (n/2), '1' * (n/2*2), '1' + '0' * (n/2*2-1)
    

    If you instead always merge the smaller island into the larger, this is instead solved very quickly.

    I think it would make your complexity O(n log n).


  • 0

    You really dig into it, man. You're awesome.


Log in to reply
 

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