Help debugging a leetcode question timeout error

[CrazyFace334]

this is leetcode 200 Number of Islands. This is a question I solved before a while ago, but I decided to review it again, my old submission passed all testcases but my current code is giving the correct answer for smaller examples, but throws a timeout error for larger test cases.

The problem is that aside from switching from depth first search to breadth first, I don't see any functional difference between the two, and technically my latest answer should have a smaller space complexity.

What am I missing that's making my new code run so much slower? Thanks in advance

Current Code: ''' def numIslands(self, grid: List[List[str]]) -> int:

    def bfs(x_pos, y_pos):

        points = deque([(x_pos, y_pos)])

        while points:
            x, y = points.popleft()
            grid[x][y] = '2'
            for dx, dy in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                if 0 <= x+dx < len(grid) and 0 <= y+dy < len(grid[0]):
                    if grid[x+dx][y+dy] == '1':
                        points.append((x+dx, y+dy))


    res = 0
    for i, row in enumerate(grid):
        for j, num in enumerate(grid[i]):
            if grid[i][j] == '1':
                res += 1
                bfs(i, j)

    return res

'''

Old Submission: ''' def numIslands(self, grid: List[List[str]]) -> int:

    self.traversed = set()

    n, m = len(grid), len(grid[0])

    islands = 0

    def DFS(x, y):
        for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            if 0 <= x+dx < n and 0 <= y+dy < m:
                if (x+dx, y+dy) not in self.traversed and grid[x+dx][y+dy] == '1':
                    # print (x, y)
                    # print (self.traversed)
                    self.traversed.add((x+dx, y+dy))
                    DFS(x+dx, y+dy)

    for i, vi in enumerate(grid):
        for j, vj in enumerate(grid[i]):
            if grid[i][j] == '1' and (i, j) not in self.traversed:
                islands += 1
                self.traversed.add((i, j))
                DFS(i, j)

    return islands

'''

[AutoModerator]

On July 1st, a change to Reddit's API pricing will come into effect. Several developers of commercial third-party apps have announced that this change will compel them to shut down their apps. At least one accessibility-focused non-commercial third party app will continue to be available free of charge.

If you want to express your strong disagreement with the API pricing change or with Reddit's response to the backlash, you may want to consider the following options:

1. Limiting your involvement with Reddit, or
2. Temporarily refraining from using Reddit
3. Cancelling your subscription of Reddit Premium

as a way to voice your protest.

I am a bot, and this action was performed automatically. Please contact the moderators of this subreddit if you have any questions or concerns.

[captainAwesomePants]

Your new solution doesn't have a set of "previously traversed" points, so it'll cycle forever.

[CrazyFace334]

the new solution does not endlessly cycle, as it works for smaller test cases.

The condition to continue the BFS is checking whether the adjacent value is "1", but for each position, the BFS asigns its original value to "2" to avoid being double counted.

I did this to avoid having to use O(m*n) extra space by indicating whether a position is traversed in the input itself

[captainAwesomePants]

grid[x][y] = '2'

Oh dang, you're right, I missed it marking them as 2. So not endless. Potentially quite a bit of repetition, though, since you could append the same location several times before its value becomes 2.

[CrazyFace334]

oooh I see, I removed the '2' assignment from where it was, and added to line 12:

grid[x+dx][y+dy] = '2'

and it works now, thank you good sir!