Accepted O(MN) Solution: linear time to the number of elements in the grid


  • 0
    H
    class Solution:
        # @param grid, a list of list of characters
        # @return an integer
        def numIslands(self, grid):
            # How many connected components?
            # Region rowing Starting with a '1', until all its four neighbor have been visited, we finished one island, count += 1
            # How to find staring '1's? Keep a hashset set1 to keep all 1s in the first scan,  when visit an island, delete corresponding 1s in the hashset
            # How to grow region? Find (r,c)'s four neighbors left/top/right/bottom (r, c-1), (r-1, c), (r, c+1), (r+1, c), remember to check boundray
            # Iterate until the set1 is empty
            #
            # We could either delete the visited 1s from the hash set, or mark it as value 2(integer) or 0(binary)?
            # 
            if not grid: #empty
                return 0
            R, C = len(grid), len(grid[0])
            set1 = set() # hash set
            for r in range(R):
                for c in range(C):
                    if grid[r][c] == "1":
                        set1.add((r,c))
            rOffset = [0, -1, 0, 1];
            cOffset = [-1, 0, 1, 0];
            count = 0 # current label for island, island is marked as 2 for the 1st iland, 3 for the 2nd one, etc.
            while set1: 
                # loop until no 1s left in the hash set 
                # Find current island connected to (r,c), delete all those elements from set1
                count += 1
                r, c = set1.pop()
                # find all 1s in current island that contains r, c
                s = [] # stack
                s.append((r,c))
                while s:
                    r, c = s.pop()
                    # all four nighbors of (r,c)
                    for i in range(len(rOffset)):
                        r2, c2 = r + rOffset[i], c + cOffset[i]
                        if (r2>=0) and (r2<R) and (c2>=0) and (c2<C) and ((r2,c2) in set1):
                            set1.remove((r2,c2))
                            s.append((r2,c2))
            return count

  • 0
    H

    I used one hashset and one stack.
    I believe it can be simplified.
    Your suggestions will be highly appreciated.


Log in to reply
 

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