What is num island and why does it appear in technical interviews
The num island problem (often titled "Number of Islands") asks you to count distinct connected groups of 1s in a 2D grid of 0s and 1s. Interviewers use num island because it tests core skills: graph traversal, boundary handling, state tracking, and clear complexity reasoning. It’s a compact way to evaluate whether you can translate a grid into a graph model, choose the right traversal (DFS/BFS/Union-Find), and defend trade-offs under pressure interviewing.io GeeksforGeeks.
Why it’s common
It’s language-agnostic and easy to verbalize.
Variants let interviewers probe follow-ups (diagonal vs. orthogonal adjacency, dynamic updates, large inputs).
Companies across the spectrum—startups to FAANG-level—use it to evaluate baseline algorithmic fluency neetcode.io leetcode.
How is num island defined and what constraints should I clarify in an interview
When an interviewer says num island, clarify these points immediately:
Input: 2D grid (matrix) of characters or integers where '1' = land and '0' = water.
Adjacency: Islands are formed by horizontally and vertically connected lands. Diagonals do not connect islands unless explicitly allowed; confirm this because it changes neighbor logic algo.monster.
Mutability: Ask whether you can modify the input grid (mark visited by overwriting '1' to '0') or must use extra space to track visited cells.
Grid size and constraints: Ask about the maximum rows/columns (n × m) to reason about complexity and stack depth for recursion.
Edge cases: Empty grid, single row/column, all water or all land.
Being explicit about these constraints early demonstrates communication and prevents wasted time debugging wrong assumptions.
How can I solve num island with Depth First Search DFS
Concept
Treat each '1' encountered during a scan as a potential island root.
Use DFS to flood-fill connected land, marking visited cells so they aren’t counted again.
High-level steps
Initialize count = 0.
Iterate every cell (i, j). When grid[i][j] == '1':
Increment count.
Run DFS from (i, j) to mark all reachable land (change to '0' or mark visited).
Continue scanning until done.
Pseudocode
Stack or recursion DFS:
If using recursion, guard against deep recursion for large grids.
Typical neighbor set: up, down, left, right.
Why DFS works
It visits all cells in a connected component before returning, ensuring each island is counted exactly once.
Simple to explain and implement in an interview GeeksforGeeks.
When to use DFS
When you want simple, readable code quickly.
When the grid size is moderate and recursion depth is safe.
When interviewer values clarity and correctness over micro-optimizations.
Common implementation tips
Always check bounds before accessing grid cells.
Use iterative stack if recursion depth may exceed language limits.
Decide early whether to mutate input or maintain a visited boolean grid.
How can I solve num island with Breadth First Search BFS
Concept
BFS achieves the same flood-fill goal as DFS but uses a queue to expand layer by layer.
High-level steps
Iterate through every cell. On '1':
Increment count.
Enqueue the cell and mark visited.
While queue not empty, dequeue and push valid 4-direction neighbors that are '1'.
Continue scanning.
Why choose BFS
Avoids recursion depth issues entirely.
Often easier to reason about iterative queue mechanics for interviewers new to recursion.
Performance (time complexity) matches DFS: O(n × m) interviewing.io.
Implementation tips
Use a simple queue (collections.deque in Python).
Mark visited when enqueuing to avoid duplicate inserts.
Explore neighbors in up/down/left/right order and never diagonal unless specified.
How can I solve num island using Disjoint Set Union Union Find
When to use Union-Find
When you want near-constant-time queries for connectivity or expect many dynamic connectivity operations (e.g., incremental updates).
For candidates aiming for advanced responses or follow-up optimization questions, Union-Find shows depth and alternative thinking neetcode.io.
Approach
Treat each cell as a node. Union adjacent lands.
After unions finish, count unique root parents for land cells.
Steps
Map 2D indices to 1D ids: id = r * cols + c.
Initialize DSU for all cells; optionally only initialize land cells.
For each land cell, union with its right and down neighbors if they are land (avoid duplicate unions).
Count distinct parents for land nodes.
Complexity and trade-offs
Union-Find tends to use extra memory but supports fast merges.
Slightly more code/setup than DFS/BFS, but it’s robust for large input sizes and union-heavy variants.
What is the time and space complexity for num island and why does it matter
Time Complexity
All main approaches (DFS, BFS, Union-Find) visit each cell a constant number of times, yielding O(n × m) where n is rows and m is columns interviewing.io GeeksforGeeks.
Space Complexity
DFS recursion: worst-case O(n × m) call stack if the grid is one big island.
BFS queue: O(n × m) worst-case if many cells are enqueued.
Visited boolean array: O(n × m) if you choose not to mutate input.
Union-Find arrays: O(n × m) for parent and rank arrays.
Why articulate these in interviews
Interviewers look for clear complexity reasoning and awareness of edge cases (stack overflow, memory limits).
Mention real constraints: if rows or columns can be >10k, recursion may be unsafe; propose iterative alternatives.
What common mistakes do candidates make with num island and how do I avoid them
Frequent errors
Accessing grid out of bounds: Check indices before grid access.
Counting diagonal neighbors: Many mistakenly include diagonals; confirm adjacency rules algo.monster.
Forgetting to mark visited: Leads to infinite loops or overcounts.
Not handling empty inputs or single-row/column grids.
Not discussing whether you can modify input; interviewers may expect the trade-off discussion.
How to avoid them
State your assumptions aloud (mutability, adjacency).
Write neighbor checks as a loop over a neighbor list [(0,1),(0,-1),(1,0),(-1,0)] to avoid accidental diagonals.
Demonstrate boundary checks in code and test them with examples.
Use small examples to validate your logic before writing full code in the interview.
How should I communicate my num island approach during an interview
Start with a clear plan
Describe input and confirm constraints: data types, adjacency, and mutability.
Present the high-level idea: "I'll scan the grid and flood-fill every unvisited '1' to count islands."
Explain choice of algorithm: DFS for simplicity, BFS for iterative safety, Union-Find for dynamic or high-performance contexts.
Give complexity analysis upfront: O(n × m) time and O(n × m) worst-case space.
While coding
Narrate each step and speak about edge cases before finishing.
After coding, walk through a small example by hand.
Point out trade-offs explicitly: "I will mutate input to save memory; if you’d prefer immutable input, I can add a visited array."
Handling follow-ups
If asked to support diagonal adjacency, show how neighbor offsets change.
If asked to optimize memory, propose in-place marking as '0' with clear caveats.
If asked for on-the-fly updates (toggle cell from 0 to 1), suggest Union-Find to maintain connectivity efficiently.
How can I practice num island effectively before interviews
Practice strategy
Start by implementing DFS and BFS variants for num island in your preferred language.
Time-box practice: 20 minutes to implement, 5 minutes for complexity and edge cases.
Solve variations: allow diagonals, count largest island size, and dynamic toggles.
Use platforms: run problems on LeetCode (Number of Islands) to get a sense of common constraints and test cases leetcode.
Drill checklist
Can I explain the approach in under 60 seconds?
Can I write correct code in 10–20 minutes with tests?
Can I discuss space/time trade-offs and alternative data structures like Union-Find?
How can Verve AI Copilot help you with num island
Verve AI Interview Copilot gives interactive, real-time coaching for num island practice. Verve AI Interview Copilot can simulate interview prompts, provide step-by-step feedback on DFS/BFS/Union-Find solutions, and suggest clearer ways to explain complexity. Verve AI Interview Copilot helps you rehearse boundary checks and follow-up changes, and provides curated test cases to validate your code. Try it at https://vervecopilot.com to get tailored num island training with immediate feedback from Verve AI Interview Copilot
What are the most important variations of num island I should be ready for
Diagonal adjacency allowed: Change neighbor offsets; results differ significantly.
Count largest island: Track max component size during flood-fill.
Perimeter of islands: Sum exposed edges during traversal.
Dynamic updates: Toggle land/water frequently — consider Union-Find or dynamic graph structures.
Multiple islands merging: After updates, answer connectivity queries — a classic Union-Find use case.
What Are the Most Common Questions About num island
Q: Can I modify the grid in num island
A: Yes if permitted; in-place marking to '0' saves O(nm) space versus a visited array
Q: Do diagonal connections count for num island
A: By default no, islands connect only up/down/left/right unless specified otherwise
Q: Which is better for num island DFS BFS or Union Find
A: DFS/BFS are simpler; Union-Find is best for dynamic or repeated connectivity queries
Q: What is the worst case time complexity for num island
A: O(n × m) because each cell is visited a constant number of times by DFS/BFS
Final checklist for presenting num island in an interview
Confirm adjacency rules and mutability at the start.
State your high-level approach and complexity before coding.
Choose DFS for rapid implementation, BFS for iterative clarity, or Union-Find for advanced follow-ups.
Handle bounds and visited marking explicitly.
Run a quick hand-trace on a small grid and discuss edge cases.
If pressed about memory or recursion, offer iterative or Union-Find alternatives.
References
Problem overview and interview context from Interviewing.io interviewing.io
DFS implementation and explanation from GeeksforGeeks GeeksforGeeks
Solution variations and walkthroughs from NeetCode and LeetCode neetcode.io leetcode
