Number of Islands

Here's an explanation of the thought process behind the solution of counting the number of islands in a grid.

Problem Understanding

The problem involves finding the number of distinct islands in a grid. An island is defined as a group of '1's (land) connected horizontally or vertically. The grid is surrounded by water ('0').

Approach

To solve this problem, I have used a graph traversal technique. Each '1' in the grid can be considered as a node, and connections (edges) exist between horizontally or vertically adjacent '1's.

Solution

from typing import List
import collections

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        """
        Given a 2D grid of '1's (land) and '0's (water), count 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.

        :param grid: List of List of str, representing the 2D grid map
        :return: Integer, the number of islands in the grid
        """
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        visit = set()
        islands = 0

        def bfs(r, c):
            """
            Perform Breadth-First Search to visit all parts of the island starting from (r, c).
            """
            q = collections.deque()
            visit.add((r, c))
            q.append((r, c))

            while q:
                row, col = q.popleft()  # Remove the oldest item from the queue (BFS)
                directions = [[1, 0], [-1, 0], [0, 1], [0, -1]]  # right, left, above, below

                for dr, dc in directions:
                    new_row, new_col = row + dr, col + dc
                    if (new_row in range(rows) and
                        new_col in range(cols) and
                        grid[new_row][new_col] == "1" and
                        (new_row, new_col) not in visit):
                        q.append((new_row, new_col))
                        visit.add((new_row, new_col))

        for r in range(rows):
            for c in range(cols):
                if grid[r][c] == "1" and (r, c) not in visit:
                    bfs(r, c)
                    islands += 1

        return islands

Strategy

1. Grid Traversal: Traverse the entire grid.
2. Breadth-First Search (BFS): For each '1' that hasn't been visited, initiate a BFS to mark all connected '1's (nodes) as visited. This traversal marks an entire island.
3. Count Islands: Each BFS initiation indicates finding a new island, so increment the island count for each BFS initiation.

Detailed Steps

1. Initial Checks: If the grid is empty, return 0.
2. Grid Dimensions: Determine the number of rows and columns in the grid.
3. Visited Set: Use a set to keep track of visited nodes to avoid counting the same island multiple times.
4. BFS Function: Define a BFS function that:
   • Uses a queue to explore all nodes (cells) connected to the starting node.
   • Adds all connected '1's to the visited set and queue.
5. Main Loop: Iterate through each cell in the grid:
   • If the cell is '1' and not visited, it's the start of a new island.
   • Call BFS to mark all connected nodes and increment the island count.
6. Return Count: After processing all cells, return the total number of islands.

Time Complexity

The time complexity of this solution is O(M×N), where M is the number of rows and N is the number of columns in the grid. Here's a detailed breakdown:

    Grid Traversal: The outer loops traverse the entire grid once, visiting each cell exactly once. This gives us O(M×N).

    BFS Traversal: In the worst case, BFS will visit all cells connected to a starting cell that forms an island. Since each cell is visited once during BFS and each cell is part of at most one island, the total number of cells visited during all BFS operations is also O(M×N).

Space Complexity

The space complexity is O(M×N) which accounts for several components:

    Visited Set: In the worst case, all cells are '1's, and the visit set will store M×N cells. Thus, this takes O(M×N) space.

    The queue for BFS: In the worst case, the queue might hold all cells of the largest island. In the worst case, this could be up to M×N cells as well. Hence, the space complexity for the queue is O(M×N).

    Recursive Stack for BFS: Although the BFS implementation provided uses an iterative approach with a queue, if it were a recursive implementation, the recursion stack would be considered. However, since it uses a queue, we don't have the additional space complexity from recursion.

Unit Tests

import unittest
class TestNumIslands(unittest.TestCase):
    """
    test_empty_grid: Tests the function with an empty grid.
    test_single_element_grid_water: Tests the function with a grid containing a single water element.
    test_single_element_grid_land: Tests the function with a grid containing a single land element.
    test_no_islands: Tests the function with a grid with no islands (all water).
    test_one_island: Tests the function with a grid containing one island.
    test_multiple_islands: Tests the function with a grid containing multiple islands.
    test_large_grid: Tests the function with a larger grid containing multiple islands.
    test_complex_island_shapes: Tests the function with a grid containing complex island shapes.
    """

    def setUp(self):
        """This method initializes a Solution instance before each test method is run."""
        self.solution = Solution()

    def test_sample(self):
        grid = [
            ["1","1","1","1","0"],
            ["1","1","0","1","0"],
            ["1","1","0","0","0"],
            ["0","0","0","0","0"],
        ]
        self.assertEqual(self.solution.numIslands(grid), 1)

    def test_empty_grid(self):
        grid = []
        self.assertEqual(self.solution.numIslands(grid), 0)

    def test_single_element_grid_water(self):
        grid = [["0"]]
        self.assertEqual(self.solution.numIslands(grid), 0)

    def test_single_element_grid_land(self):
        grid = [["1"]]
        self.assertEqual(self.solution.numIslands(grid), 1)

    def test_no_islands(self):
        grid = [
            ["0", "0", "0"],
            ["0", "0", "0"],
            ["0", "0", "0"]
        ]
        self.assertEqual(self.solution.numIslands(grid), 0)

    def test_one_island(self):
        grid = [
            ["1", "1", "0"],
            ["1", "1", "0"],
            ["0", "0", "0"]
        ]
        self.assertEqual(self.solution.numIslands(grid), 1)

    def test_multiple_islands(self):
        grid = [
            ["1", "0", "0", "1", "0"],
            ["1", "0", "0", "1", "0"],
            ["0", "0", "0", "0", "1"],
            ["0", "1", "1", "0", "0"]
        ]
        self.assertEqual(self.solution.numIslands(grid), 4)

    def test_large_grid(self):
        grid = [
            ["1", "1", "1", "0", "0", "0", "1", "1", "1"],
            ["1", "1", "0", "0", "0", "0", "1", "1", "1"],
            ["1", "1", "0", "0", "1", "1", "0", "0", "0"],
            ["0", "0", "0", "0", "1", "1", "0", "0", "0"]
        ]
        self.assertEqual(self.solution.numIslands(grid), 3)

    def test_complex_island_shapes(self):
        grid = [
            ["1", "0", "1", "0"],
            ["1", "1", "0", "1"],
            ["0", "1", "1", "0"],
            ["0", "0", "1", "1"]
        ]
        self.assertEqual(self.solution.numIslands(grid), 3)

if __name__ == "__main__":
    unittest.main()

The provided unit tests ensure the solution handles various edge cases:

•     Empty grids
•     Single-element grids
•     Grids with no islands
•     Grids with one or multiple islands
•     Large grids
•     Complex island shapes

These tests ensure the solution is accurate and can handle different scenarios effectively.