200.Number_of_Islands_(Medium).md

200. Number of Islands (Medium)

Date and Time: Jun 20, 2024, 17:21 PM (EST)

Link: https://leetcode.com/problems/number-of-islands/

Question:

Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input: grid = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]

Output: 1

Example 2:

Input: grid = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]

Output: 3

Walk-through:

Loop over all the grids in the board to check if each grid is in visited() or not, if not and grid[r][c] == 1 we can cache all its neighbors by BFS starting from this grid and increment islands by '1' ('1' is string), because this continent of island has not been visited before.

DFS Solution:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # Run DFS from an entry = 1, mark all the connected island in visited(), each time we have a new entry = 1, increment cnts
        
        # TC: O(m*n), SC: O(m*n)
        visited = set()
        ans = 0
        rows, cols = len(grid), len(grid[0])
        directions = [[-1, 0], [1, 0], [0, 1], [0, -1]]
        # Run DFS to mark all entries in one island to be visited
        def dfs(r, c):
            visited.add((r, c))
            for dr, dc in directions:
                row, col = r+dr, c+dc
                if row in range(rows) and col in range(cols) and (row, col) not in visited and grid[row][col] == '1':
                    dfs(row, col)
        # Find islands
        for r in range(rows):
            for c in range(cols):
                if (r, c) not in visited and grid[r][c] == '1':
                    ans += 1
                    dfs(r, c)
        return ans

Time Complexity: $O(m * n)$, we are checking each grid in grid.
Space Complexity: $O(m * n)$, we need to store all grid in visited.

BFS Solution:

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        visited = set()
        islands = 0
        rows, cols = len(grid), len(grid[0])

        def bfs(r, c):
            deque = collections.deque()
            deque.append((r, c))
            visited.add((r, c))  # now they are visited
            while deque:
                row, col = deque.pop()
                directions = [[1, 0], [-1, 0], [0, -1], [0, 1]]  # N,S,W,E
                for dr, dc in directions:
                    r, c = row + dr, col + dc
                    # Check if four directions of current position are valid
                    if r in range(rows) and c in range(cols) and grid[r][c] == '1' and (r, c) not in visited:
                        deque.append((r, c))
                        visited.add((r, c))
        # Perform BFS, 'cache' all the neighboring grids, if found not in the cache, islands += 1
        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == '1' and (r, c) not in visited:
                    bfs(r, c)
                    islands += 1
        return islands

Time Complexity: $O(m * n)$, we are checking each grid in grid.
Space Complexity: $O(m * n)$, we need to store all grid in visited.

C++ Solution:

1. C++ uses {} as [] in Python.

2. const auto& [r, c]: directions to unpack row and col from directions as r, c.

class Solution {
private:
    set<pair<int, int>> visited;
    vector<pair<int, int>> directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

public:
    int numIslands(vector<vector<char>>& grid) {
        // Run DFS on each entry with a visited() to store all the entries of the island
        int cnts = 0;
        int rows = grid.size();
        int cols = grid[0].size();
        // Find number of islands
        for (int r=0; r < rows; r++) {
            for (int c=0; c < cols; c++) {
                if (grid[r][c] == '1' && !visited.contains({r, c})) {
                    cnts++;
                    dfs(r, c, grid);
                }
            }
        }
        return cnts;
    }

    // Run DFS to mark all entries in an island to be visited
    void dfs(int r, int c, vector<vector<char>>& grid) {
        visited.insert({r, c});
        int rows = grid.size();
        int cols = grid[0].size();
        for (const auto& [dr, dc]: directions) {
            int row = r + dr;
            int col = c + dc;
            // Check if neighbors are valid to visit
            if (row >= 0 && row < rows && col >= 0 && col < cols && grid[row][col] == '1' && !visited.contains({row, col})) {
                dfs(row, col, grid);
            }
        }
    }
};

Runtime and Memory comparison

Language	Runtime	Memory
Python3	315 ms	24.2 MB
Java	ms	MB
C++	71 ms	24.5 MB