Number of Islands

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

What is Being Asked?

(One sentence on the actual task.)

Key Observations

(Patterns, constraints, or hints in the problem statement.)

Approach Taken

(Step-by-step logic or pseudocode before coding.)

Why This Works

(Explain the core reason the solution is correct.)

Main Concepts Used

(Mark the CS concepts or algorithms used.)

Time & Space Complexity

• Time: $O()$ → Reason:
• Space: $O()$ → Reason:

Code

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # DFS from each unvisited land
        # land is 1
        # doesnt exist in visited set
        # go up,down,left and right using dfs
        # cannot go diagonal
        # keep result global variable

        self.visited = set()
        self.countOfIslands = 0

        def dfs(row, col):
            if row < 0 or col < 0 or row == len(grid) or col == len(grid[0]):
                return
            if (row, col) in self.visited:
                return
            if grid[row][col] == "0":
                return

            self.visited.add((row,col))
            dfs(row - 1, col)
            dfs(row + 1, col)
            dfs(row, col - 1)
            dfs(row, col + 1)

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if (row, col) in self.visited:
                    continue
                
                if grid[row][col] == "1":
                    dfs(row, col)
                    self.countOfIslands += 1

        return self.countOfIslands

Common Mistakes / Things I Got Stuck On

Optimal Solution $O(1)$ space

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        self.countOfIslands = 0

        def dfs(row, col):
            if row < 0 or col < 0 or row == len(grid) or col == len(grid[0]):
                return
            if grid[row][col] == "0" or grid[row][col] == "#":
                return

            grid[row][col] = "#"
            dfs(row - 1, col)
            dfs(row + 1, col)
            dfs(row, col - 1)
            dfs(row, col + 1)

        for row in range(len(grid)):
            for col in range(len(grid[0])):
                if grid[row][col] == "#":
                    continue
                
                if grid[row][col] == "1":
                    dfs(row, col)
                    self.countOfIslands += 1

        return self.countOfIslands