What if we can only read line by line? - Real interview question in YAHOO!


  • 3
    J

    This question itself is a very common DFS.
    I give an answer when I was having interview in Yahoo, Flickr in seconds.

    Then the following up is, what if the matrix is very big?
    The interviewer might want an answer around like sparse matrix. But I come out a naive thinking of read line by line. I did not work it out in interview in 30 mins. But I did not give up after interview. Now I think I got a way. As following.

    I use a concept of "color", which is still a kind of dfs. But the connection is implemented by hashtable and the size of hashtable is limited to O(n). So, it's O(n) space complexity in all.(rather than O(n^2))

    Let me explain it as following:
    "1111111"
    "0000001"
    "1111101"
    "1000101"
    "1010101"
    "1011101"
    "1111111"
    Suppose a matrix as above. We are gonna read them one line each time.

    line 0-1
    "1111111"
    "0000001"
    land in Line 1 is colored by island in line 0 as island 1.

    line 1-2
    "0000001"
    "2222201"
    Line 2 is colored by island in line 1 and got another island. Will the another island be colored later? Let's see.

    line 2-3
    "2222201"
    "2000201"
    Similar as above

    line 3-4
    "2000201"
    "2030201"
    Similar as above. Now we got island 3.We count as we have 3 islands in total.

    line 4-5
    "3(2)0303(2)01"
    "3(2)033301"
    Here, we found island 3 and island 2 are connected! So we color all island 2 to island 3(vice versa is also available) and minus 1 in our count of island

    line 5-6
    "3033303(1)"
    "3333333"
    Then island 1 and island 3 are connected, we minus 1 on total again!

    Then we got island total as 1!

    class Solution(object):
        def numIslands(self, grid):
            """
            :type grid: List[List[str]]
            :rtype: int
            """
            
            #Increase itself
            c = 0
            
            def generateInterval(line):
                invArr = []
                i = 0
                while i<len(line):
                    if line[i] == '1':
                        newInv = {'start':i}
                        while i<len(line) and line[i] == '1' :
                            i+=1
                        newInv['end'] = (i-1)
                        invArr.append(newInv)
                    i += 1
                return invArr
                
            lastLineInvArr = []
             
            islandColorId = 1
            for line in grid:
                p = 0
                curInvArr = generateInterval(line)
                
                colorTransMap = {}
                j = 0
                for j in range(0, len(curInvArr)):
                    curInv = curInvArr[j]
                    while p<len(lastLineInvArr) and lastLineInvArr[p]['end']<curInv['start']:
                        p += 1
                    
                    if p>=len(lastLineInvArr):
                        break
                    
                    if curInv['end'] < lastLineInvArr[p]['start']:
                        c += 1
                        curInv['color'] = islandColorId
                        islandColorId+=1
                        continue
                    
                    while p<len(lastLineInvArr) and curInv['end']>=lastLineInvArr[p]['start']:
                        if not 'color' in curInv:
                            if lastLineInvArr[p]['color'] in colorTransMap:
                                lastLineInvArr[p]['color'] = colorTransMap[lastLineInvArr[p]['color']]
                            curInv['color'] = lastLineInvArr[p]['color']
                        else:
                            if not lastLineInvArr[p]['color']==curInv['color'] and lastLineInvArr[p]['color'] not in colorTransMap:
                                c -= 1
                                colorTransMap[lastLineInvArr[p]['color']] = curInv['color']
                                lastLineInvArr[p]['color'] = curInv['color']
                            
                        if curInv['end'] >= lastLineInvArr[p]['end']:
                            p+=1
                        else:
                            break
                
                while j<len(curInvArr):
                    if 'color' not in curInvArr[j]:
                        c += 1
                        curInvArr[j]['color'] = islandColorId
                        islandColorId += 1
                    j += 1
            
                for curInv in curInvArr:
                    if curInv['color'] in colorTransMap:
                        curInv['color'] = colorTransMap[curInv['color']]    
                
                lastLineInvArr = curInvArr
                      
            return c
    

  • 0
    Z

    @jun6 How does your algorithm speed up the sparse matrix traversal? By "n" in O(n), do yo mean the size of Matrix or the size of a row(line)?


  • 0
    J

    @zhangsikai123
    Not speed, but reduce the space needed.

    Later I understand my method is called union find.
    You can check out for "union find".

    Right here
    https://leetcode.com/problems/number-of-islands-ii/#/description


Log in to reply
 

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