Count Sub Islands
Medium · Graphs · Array · Depth-First Search · Breadth-First Search · Union Find · Matrix
Problem
You are given two m x n binary matrices grid1 and grid2, where 1 is land and 0 is water. An island is a group of land cells connected up, down, left or right; cells outside the grid are water.
An island in grid2 is a sub-island if every one of its cells is also land in grid1. Return the number of islands in grid2 that are sub-islands.
Examples
Input: grid1 = [[1,1,0],[1,1,0],[0,0,1]], grid2 = [[1,0,0],[1,0,1],[0,0,1]] Output: 1
The left island of grid2, cells (0,0) and (1,0), lies on land in grid1. The right island includes (1,2), which is water in grid1.
Input: grid1 = [[1,1],[1,1]], grid2 = [[1,0],[0,1]] Output: 2
grid2 has two one-cell islands (diagonal cells are not connected), and both sit on land.
Input: grid1 = [[0]], grid2 = [[1]] Output: 0
The island of grid2 is over water in grid1.
Constraints
- m == len(grid1) == len(grid2)
- n == len(grid1[i]) == len(grid2[i])
- 1 <= m, n <= 500
- every cell is 0 or 1
Approaches
- Rediscover the island from every cell — time O((m · n)²) in the worst case, space O(m · n)
Follow-up
If cells of grid2 were switched on one at a time and you had to report the number of sub-islands after each step, a union-find over the land cells works: each set keeps a flag for “has a cell over grid1 water”, and merging two sets combines the flags.
Related problems
Start free on Cariara · Coding problems · System design studio
