← Visualizers
Graphs · Dual-grid lockstep traversal LeetCode 1905

Count Sub-Islands / visualized

An island in grid2 is a sub-island only if every one of its cells is also land in grid1. The flood fill walks grid2, but checks grid1 in lockstep. Crucial invariant: you cannot short-circuit with &&, or disqualified islands are left half-sunk and spawn phantom islands later.

Execution · Lockstep Grids

idle
INVARIANT Lockstep Traversal: You must sink the ENTIRE component in grid2 even after a mismatch is found (use bitwise & rather than &&), or unsunk pieces will be counted as new islands later!
grid1 (Base Mask)
grid2 (Flood & Sink)
Call Stack · Lockstep Verification Top = Active · Bottom = Suspended Parents
Press Run to begin.
0 / 0
Speed

Java · running line

scanning grid2 current cell confirmed sub-island disqualified component water / sunk
INTERVIEW SCRIPT

How to Explain Dual-Grid Traversal to an Interviewer

1. The Dual-Grid Contract

"We explore islands in grid2, but for each land cell, we check if grid1[r][c] == 1 in lockstep. An island is valid only if zero cells touch water in grid1."

2. The Fatal Short-Circuit Trap

"If we used isSub && d1 && d2..., as soon as one cell fails, remaining calls are skipped. That leaves the rest of the island un-sunk in grid2, causing the outer loop to find phantom islands later!"

3. Bitwise & Forces Full Sinking

"Using non-short-circuit bitwise & guarantees all 4 recursive calls execute, sinking the entire component even when we already know it is disqualified."

4. Space & Time Complexity

"Time is O(m · n) as each cell in grid2 is sunk once. Auxiliary space is bounded by the call stack depth, which is O(m · n) worst case."

O(m·n) time · O(m·n) stack  ·  evaluating isSub & d1 & d2 & d3 & d4 sinks the whole component even when disqualified, preventing false positive splits.