LeetCode 1905 - Count Sub Islands

The problem presents two m x n binary matrices, grid1 and grid2, representing maps of land (1) and water (0). Each matrix may contain multiple islands, where an island is defined as a connected group of 1s that are adjacent vertically or horizontally.

leetcodemediumarraydepth-first-searchbreadth-first-searchunion-findmatrix

LeetCode Problem 1905

Difficulty: 🟡 Medium
Topics: Array, Depth-First Search, Breadth-First Search, Union-Find, Matrix

Solution

Problem Understanding

The problem presents two m x n binary matrices, grid1 and grid2, representing maps of land (1) and water (0). Each matrix may contain multiple islands, where an island is defined as a connected group of 1s that are adjacent vertically or horizontally. The task is to determine how many islands in grid2 are sub-islands, meaning that every cell in such an island of grid2 coincides with land in grid1.

In other words, a sub-island is a portion of grid2's land that is entirely contained within some island in grid1. The expected output is a single integer, representing the count of sub-islands in grid2.

Constraints provide a matrix size up to 500 x 500, which implies up to 250,000 cells. Algorithms with O((m * n)^2) complexity are impractical, while O(m * n) solutions are feasible. Edge cases include islands in grid2 partially overlapping grid1 islands, islands that are completely disjoint, and grids with all water or all land.

Approaches

The brute-force approach would attempt to compare every island in grid2 with every island in grid1, checking if all cells match. While correct, this requires identifying and storing all islands first, then comparing cell-by-cell, leading to O((m * n)^2) complexity in the worst case. This is too slow for the maximum constraints.

The optimal approach leverages Depth-First Search (DFS) or Breadth-First Search (BFS) directly on grid2. The key insight is that as we traverse each island in grid2, we can simultaneously check whether each cell exists as land in grid1. If any cell does not match, the island cannot be a sub-island. This allows us to process each cell only once, achieving O(m * n) time complexity. DFS modifies grid2 in-place to mark visited cells, keeping space usage manageable.

Approach Time Complexity Space Complexity Notes
Brute Force O((m * n)^2) O(m * n) Identify islands separately in both grids, then compare all pairs
Optimal O(m * n) O(m * n) DFS or BFS on grid2, checking overlap with grid1 and marking visited

Algorithm Walkthrough

  1. Initialize a counter count to track the number of sub-islands.
  2. Define a DFS function that accepts coordinates (i, j). This function will recursively visit all connected land cells of grid2's island.
  3. During DFS, if a cell in grid2 is 1 but the corresponding grid1[i][j] is 0, mark a flag indicating that the current island is not a sub-island.
  4. Mark the current cell in grid2 as visited (set to 0) to avoid revisiting it.
  5. Recursively call DFS for all four neighbors (up, down, left, right) within the matrix bounds.
  6. Iterate over all cells of grid2. When an unvisited land cell is found, call DFS. If the DFS traversal confirms the island is a sub-island (no cell failed the overlap check), increment count.
  7. Return count after processing all cells.

Why it works: The DFS ensures each island in grid2 is fully traversed once. By checking against grid1 during traversal, we guarantee that only islands fully contained in grid1 are counted as sub-islands. Each cell is visited once, and no island is counted twice due to marking visited cells.

Python Solution

from typing import List

class Solution:
    def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int:
        m, n = len(grid2), len(grid2[0])
        
        def dfs(i: int, j: int) -> bool:
            if i < 0 or i >= m or j < 0 or j >= n or grid2[i][j] == 0:
                return True  # Outside or water, doesn't affect sub-island status
            grid2[i][j] = 0  # Mark visited
            is_sub = True
            if grid1[i][j] == 0:
                is_sub = False  # This cell is not land in grid1
            # Visit all four neighbors
            top = dfs(i - 1, j)
            bottom = dfs(i + 1, j)
            left = dfs(i, j - 1)
            right = dfs(i, j + 1)
            return is_sub and top and bottom and left and right
        
        count = 0
        for i in range(m):
            for j in range(n):
                if grid2[i][j] == 1:
                    if dfs(i, j):
                        count += 1
        return count

In this implementation, the DFS function returns True if the island is a sub-island. The is_sub variable is used to track whether any cell fails the sub-island check. Visiting neighbors recursively combines the sub-island status using logical AND, ensuring the entire island is validated before incrementing the count.

Go Solution

func countSubIslands(grid1 [][]int, grid2 [][]int) int {
    m, n := len(grid2), len(grid2[0])
    
    var dfs func(i, j int) bool
    dfs = func(i, j int) bool {
        if i < 0 || i >= m || j < 0 || j >= n || grid2[i][j] == 0 {
            return true
        }
        grid2[i][j] = 0
        isSub := true
        if grid1[i][j] == 0 {
            isSub = false
        }
        top := dfs(i-1, j)
        bottom := dfs(i+1, j)
        left := dfs(i, j-1)
        right := dfs(i, j+1)
        return isSub && top && bottom && left && right
    }
    
    count := 0
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid2[i][j] == 1 {
                if dfs(i, j) {
                    count++
                }
            }
        }
    }
    return count
}

The Go implementation mirrors Python closely. Recursive DFS handles marking visited cells and validating sub-islands. Go-specific details include explicit function variable declaration for recursion and using slices for 2D grids.

Worked Examples

Example 1:

grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]]

grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]

Iterating through grid2, the first unvisited land cell at (0,0) forms an island. DFS explores connected land. Checking overlap with grid1, the first island matches partially, so it counts as a sub-island. Continuing the traversal, other islands at (2,1) and (3,2) are similarly evaluated. In total, three sub-islands are found.

Example 2:

grid1 = [[1,0,1,0,1],[1,1,1,1,1],[0,0,0,0,0],[1,1,1,1,1],[1,0,1,0,1]]

grid2 = [[0,0,0,0,0],[1,1,1,1,1],[0,1,0,1,0],[0,1,0,1,0],[1,0,0,0,1]]

DFS checks each island in grid2. The islands at (1,0) and (4,0) are sub-islands, while cells that overlap with water in grid1 do not count. Result is two sub-islands.

Complexity Analysis

Measure Complexity Explanation
Time O(m * n) Each cell is visited once during DFS; each DFS call examines four neighbors
Space O(m * n) Recursion stack may grow proportional to the size of the largest island; grid2 is modified in place

The algorithm efficiently processes each cell exactly once, and marking visited cells ensures no redundant work.

Test Cases

# Provided examples
assert Solution().countSubIslands([[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]], 
                                   [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]) == 3
assert Solution().countSubIslands([[1,0,1,0,1