Number of Islands

Graph
Medium

Approach

Diagrams

Analysis

Time

O(mn)

Space

O(mn)
from collections import deque


class Solution:
    def numIslands(self, grid):
        numRows, numCols = len(grid), len(grid[0])
        count = 0

        visited = [[False for col in range(numCols)] for row in range(numRows)]

        for row in range(numRows):
            for col in range(numCols):
                if grid[row][col] == '0' or visited[row][col]:
                    continue

                start = (row, col)
                self.bfs(start, visited, grid, numRows, numCols)
                count += 1

        return count

    def bfs(self, start, visited, grid, numRows, numCols):
        queue = deque([start])

        row, col = start
        visited[row][col] = True

        while queue:
            node = queue.popleft()
            neighbors = self.getNeighbors(node, numRows, numCols)

            for neighbor in neighbors:
                row, col = neighbor

                if grid[row][col] == '0' or visited[row][col]:
                    continue

                queue.append(neighbor)
                visited[row][col] = True

    def getNeighbors(self, coord, numRows, numCols):
        row, col = coord
        neighbors = []

        deltaRow = [-1, 0, 1, 0]
        deltaCol = [0, 1, 0, -1]

        for delta in range(len(deltaRow)):
            neighborRow = row + deltaRow[delta]
            neighborCol = col + deltaCol[delta]

            isValid = 0 <= neighborRow < numRows and 0 <= neighborCol < numCols

            if isValid:
                neighbors.append((neighborRow, neighborCol))

        return neighbors

Learn

#Breadth-First Search

Videos