CODEWITHSUNDEEP
pythonbreadth-first-searchtime-limiting
R__
R__

Reputation: 87

Time Limit Exceed for BFS algorithm

It is leetcode #200, number of islands. My code is

def numIslands(self, grid: List[List[str]]) -> int:
        def bfs(i,j):
            q = deque([[i,j]])
            while q:
                r,c = q.popleft()
                if 0<=r<len(grid) and 0<=c<len(grid[0]) and grid[r][c]=="1":
                    grid[r][c]="0"
                    q += [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j]=="1":
                    count+=1
                    bfs(i,j)

        return count

It works fine. But when I change the bfs function into

def bfs(i,j):
    q = deque([[i,j]])
    while q:
        r,c = q.popleft()
        grid[r][c]="0"
        for d in [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]:
            if 0<=d[0]<len(grid) and 0<=d[1]<len(grid[0]) and grid[d[0]][d[1]]=="1":
                q.append(d)

It gives me the Time Limit Exceeded error, what could the reasons be? I think these two codes are nearly identical?

Upvotes: 1

Views: 114

Answers (1)

joaopfg
joaopfg

Reputation: 1287

You are visiting the same state many times:

Change to the following:

def bfs(i,j):
    q = deque([[i,j]])
    grid[i][j]="0"

    while q:
        r,c = q.popleft()
        for d in [[r + 1, c], [r - 1, c], [r, c - 1], [r, c + 1]]:
            if 0<=d[0]<len(grid) and 0<=d[1]<len(grid[0]) and grid[d[0]][d[1]]=="1":
                grid[d[0]][d[1]]="0"
                q.append(d)

Upvotes: 1

Related Questions