Count Sub Islands

Count Sub Islands

What is this problem about?

The "Count Sub Islands interview question" is a 2D grid problem. You are given two $m imes n$ binary matrices, grid1 and grid2, representing land (1) and water (0). An island in grid2 is considered a "sub-island" if every single cell of that island is also part of an island in grid1. You need to count the total number of such sub-islands in grid2.

Why is this asked in interviews?

Companies like Amazon and Google use the "Count Sub Islands coding problem" to test a candidate's proficiency with Graph Traversal (DFS/BFS). It adds a layer of complexity to the standard "Number of Islands" problem by requiring you to validate a condition across two different grids simultaneously. It evaluations your ability to maintain state across multiple cells during a traversal.

Algorithmic pattern used

This problem is solved using the Flood Fill or DFS/BFS pattern.

1. Iterate: Loop through every cell in grid2.
2. Island Discovery: When you find a 1 in grid2 that hasn't been visited, start a DFS/BFS to explore the entire island.
3. Sub-island Validation: During the traversal of the island in grid2, check each cell $(r, c)$ against grid1[r][c].
   • If grid1[r][c] is 0, then this island in grid2 is NOT a sub-island.
   • You must continue the traversal to mark all cells of the island as visited, even if you already know it's not a sub-island.
4. Counting: Increment your counter only if the entire traversal completes without finding a mismatch in grid1.

Example explanation

grid1:

1 1 1
1 0 0

grid2:

1 1 0
0 0 1

• Island A in grid2: {(0,0), (0,1)}. Both are 1 in grid1. Sub-island! (Count = 1).
• Island B in grid2: {(1,2)}. But grid1[1][2] is 0. Not a sub-island. Result: 1.

Common mistakes candidates make

• Early Exit: Stopping the DFS as soon as a cell in grid1 is found to be 0. This is a mistake because you need to visit and "sink" all parts of the island in grid2 to avoid re-discovering them later in the loop.
• Visited State: Not correctly marking cells as visited (e.g., by changing them to 0 or using a separate boolean matrix).
• Confusion between grids: Checking grid2 against grid1 incorrectly or swapping their roles.

Interview preparation tip

Master the "Island Pattern." Problems involving connected components in a matrix are extremely common. Practice implementing DFS both recursively and iteratively, as some interviewers may ask about stack limits for large grids.