LeetCode 305: Number of Islands II Solution in Python – A Step-by-Step Guide

What Is LeetCode 305: Number of Islands II?

In LeetCode 305: Number of Islands II, you’re given a grid size (m x n) initially all water (0s) and a list of positions where land (1s) is added one-by-one. After each addition, you return the current number of islands—disconnected land regions connected by up, down, left, or right moves (no diagonals). For example, with m=3, n=3, and positions=[(0,0), (0,1), (1,2), (2,1)], the island counts evolve as land connects. This problem tests your ability to track dynamic changes, building on LeetCode 200: Number of Islands with real-time updates.

Problem Statement

• Input: Integers m (rows) and n (cols), list positions (land coordinates).
• Output: A list of integers—number of islands after each position is added.
• Rules: Land connects horizontally/vertically; count distinct islands; grid starts as water.

Constraints

• m, n: 1 to 300.
• positions length: 0 to min(m * n, 10⁴).
• Positions are unique and within bounds.

Examples

• Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
• Output: [1,1,2,3]
• Input: m = 1, n = 1, positions = [[0,0]]
• Output: [1]
• Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,1]]
• Output: [1,1,1]

Understanding the Problem: Counting Islands Dynamically

To solve LeetCode 305: Number of Islands II in Python, we need a class or function that starts with an m x n grid of 0s and processes each new land position, returning the island count after each addition. For positions [(0,0), (0,1)], land at (0,0) makes 1 island, then (0,1) connects to it, still 1 island. A naive way might rebuild the grid and count islands each time, but that’s slow. Instead, we’ll use:

• Best Solution (Union-Find with Path Compression): O(k * α(m*n)) time (k = positions length), O(m*n) space—fast and scalable.
• Alternative Solution (DFS with Grid Updates): O(k * m * n) time, O(m*n) space—simpler but slower.

Let’s dive into the union-find solution with a friendly breakdown that’s easy to follow.

Best Solution: Union-Find with Path Compression

Why This Is the Best Solution

The union-find with path compression approach is the top choice for LeetCode 305 because it’s highly efficient—O(k * α(mn)) time (near-linear, where α is the inverse Ackermann function) and O(mn) space. It uses a disjoint-set data structure to track island connections, merging them as land connects, with path compression for speed. It’s like keeping a quick ledger of island groups—perfect for dynamic updates!

How It Works

Let’s picture this like connecting islands with bridges:

• Step 1: Set Up Union-Find:
• Use a parent array where each cell points to its island’s root.
• Track rank for balanced merging.
• Start with count = 0 (no islands).
• Step 2: Process Each Position:
• Convert (r, c) to a 1D index (r * n + c).
• Set parent[index] = index (new island), count += 1.
• Check 4 neighbors (up, down, left, right):
• If neighbor is land (in parent), union them, reducing count if merged.
• Step 3: Union and Find:
• Find: Follow parent pointers to root, compress path by pointing to root.
• Union: Merge smaller rank into larger, update count if roots differ.
• Step 4: Why It Works:
• Union-find tracks island groups efficiently.
• Path compression keeps find operations near O(1).
• Count adjusts as islands connect.

It’s like a fast island merger—track and link in a snap!

Step-by-Step Example

Example: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]

• Init: parent = [-1]*9, rank = [0]*9, count = 0, result = [].
• (0,0):
• Index = 0*3+0 = 0, parent[0] = 0, count = 1.
• Neighbors (none valid), result = [1].
• (0,1):
• Index = 0*3+1 = 1, parent[1] = 1, count = 2.
• Neighbor (0,0): Union(1, 0), parent[1] = 0, count = 1.
• Result = [1, 1].
• (1,2):
• Index = 1*3+2 = 5, parent[5] = 5, count = 2.
• No neighbors, result = [1, 1, 2].
• (2,1):
• Index = 2*3+1 = 7, parent[7] = 7, count = 3.
• Neighbor (1,2): No connect yet.
• Result = [1, 1, 2, 3].
• Result: [1, 1, 2, 3].

Code with Detailed Line-by-Line Explanation

Here’s the Python code, broken down so it’s easy to follow:

Copy codeclass Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        # Step 1: Set up union-find
        parent = [-1] * (m * n)  # -1 means water
        rank = [0] * (m * n)     # For balanced merging
        count = 0                # Island count
        result = []

        # Directions for 4 neighbors
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

        # Step 2: Find with path compression
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])  # Compress path
            return parent[x]

        # Step 3: Union with rank
        def union(x, y):
            root_x = find(x)
            root_y = find(y)
            if root_x != root_y:
                nonlocal count
                if rank[root_x] < rank[root_y]:
                    parent[root_x] = root_y
                elif rank[root_x] > rank[root_y]:
                    parent[root_y] = root_x
                else:
                    parent[root_y] = root_x
                    rank[root_x] += 1
                count -= 1  # Merged, reduce count

        # Step 4: Process each position
        for r, c in positions:
            idx = r * n + c
            if parent[idx] != -1:  # Already land, skip
                result.append(count)
                continue

            # New land
            parent[idx] = idx
            count += 1

            # Check neighbors
            for dr, dc in directions:
                nr, nc = r + dr, c + dc
                neighbor_idx = nr * n + nc
                if (0 <= nr < m and 0 <= nc < n and 
                    parent[neighbor_idx] != -1):  # Neighbor is land
                    union(idx, neighbor_idx)

            result.append(count)

        return result

• Line 4-9: Setup:
• parent: -1 for water, self-index for new land.
• rank: Balances merges.
• count: Tracks islands.
• Line 12-16: find: Returns root, compresses path by pointing to root.
• Line 19-30: union: Merges roots, adjusts rank, reduces count if merged.
• Line 33-50: Process positions:
• Line 35-38: Skip if already land.
• Line 40-41: New land, set parent, increment count.
• Line 43-48: Check 4 neighbors, union if land.
• Line 49: Append current count.
• Time Complexity: O(k * α(m*n))—k positions, near-constant find/union.
• Space Complexity: O(m*n)—parent and rank arrays.

This is like a quick island linker—merge and count fast!

Alternative Solution: DFS with Grid Updates

Why an Alternative Approach?

DFS with grid updates tracks islands by exploring each new land—O(k * m * n) time, O(m*n) space. It’s simpler but slower, updating a grid and running DFS to count islands each time, like redrawing the map—intuitive but inefficient for many updates.

How It Works

Let’s think of this as a map redraw:

• Step 1: Initialize grid of 0s.
• Step 2: For each position, set to 1, DFS to count islands.
• Step 3: Track visited cells, count disconnected 1s.

It’s like exploring the grid anew each time!

Step-by-Step Example

Example: m = 2, n = 2, positions = [[0,0],[0,1]]

• Init: [[0,0],[0,0]], count = 0.
• (0,0): [[1,0],[0,0]], DFS: 1 island, result = [1].
• (0,1): [[1,1],[0,0]], DFS: 1 island (connected), result = [1, 1].
• Result: [1, 1].

Code for DFS Approach

Copy codeclass Solution:
    def numIslands2(self, m: int, n: int, positions: List[List[int]]) -> List[int]:
        grid = [[0] * n for _ in range(m)]
        result = []

        def dfs(r, c):
            if (r < 0 or r >= m or c < 0 or c >= n or 
                grid[r][c] == 0 or (r, c) in visited):
                return
            visited.add((r, c))
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                dfs(r + dr, c + dc)

        for r, c in positions:
            grid[r][c] = 1
            visited = set()
            count = 0
            for i in range(m):
                for j in range(n):
                    if grid[i][j] == 1 and (i, j) not in visited:
                        dfs(i, j)
                        count += 1
            result.append(count)

        return result

• Time Complexity: O(k * m * n)—k DFS runs.
• Space Complexity: O(m*n)—grid and visited set.

It’s a full redraw each time!

Comparing the Two Solutions

• Union-Find (Best):
• Pros: O(k * α(m*n)) time, O(m*n) space, fast updates.
• Cons: Union-find logic.
• DFS (Alternative):
• Pros: O(k * m * n) time, O(m*n) space, simple traversal.
• Cons: Much slower.

Union-find wins big.

Additional Examples and Edge Cases

• 1,1,[[0,0]]: [1].
• 2,2,[[0,0],[1,1]]: [1, 2].
• 2,2,[[0,0]]: [1].

Union-find is faster.

Complexity Breakdown

• Union-Find: Time O(k * α(m*n)), Space O(m*n).
• DFS: Time O(k * m * n), Space O(m*n).

Union-find rules.

Key Takeaways

• Union-Find: Merge fast—smart!
• DFS: Explore all—clear!
• Grids: Dynamic updates are fun.
• Python Tip: Arrays rock—see [Python Basics](/python/basics).

Final Thoughts: Count Those Islands

LeetCode 305: Number of Islands II in Python is a dynamic grid challenge. Union-find tracks islands efficiently, while DFS redraws the map. Want more? Try LeetCode 200: Number of Islands or LeetCode 694: Number of Distinct Islands. Ready to tally? Head to Solve LeetCode 305 on LeetCode and count those islands today!