Back to course home
0% completed
Vote For New Content
Wrong BFS space complexity in solution explanation?
Tobby Lie
Sep 4, 2024
The BFS solution provided seems unnecessarily complicated, this is what I have in Python that has a space complexity of O(min(m, n)) rather than the O(m * n) described in the solution...
from collections import deque class Solution: def maxAreaOfIsland(self, matrix): biggestIslandArea = 0 rows = len(matrix) cols = len(matrix[0]) for i in range(rows): for j in range(cols): if matrix[i][j] == 1: biggestIslandArea = max(biggestIslandArea, self.visit_land_bfs(matrix, i, j)) return biggestIslandArea def visit_land_bfs(self, matrix, x, y): neighbors = deque([(x, y)]) area = 0 while neighbors: x, y = neighbors.popleft() if x < 0 or x >= len(matrix) or y < 0 or y >= len(matrix[0]): continue if matrix[x][y] == 0: continue matrix[x][y] = 0 area += 1 neighbors.append((x + 1, y)) neighbors.append((x - 1, y)) neighbors.append((x, y + 1)) neighbors.append((x, y - 1)) return area
0
0
Comments
Comments
On this page
Problem Statement
Try it yourself