Deep Dive: BFS/DFS Island Family

Learning Outcome

Build interview depth for BFS/DFS Island Family.

Pattern Recognition

Intuition

Grid components are graph components with boundary rules.

Exact Practice Question Names

• Number of Islands
• Closed Islands
• Number of Enclaves

Interview Approach

1. Start with the base family.
2. Identify the new state or constraint.
3. Show why the simpler approach fails.
4. Add the smallest extra state needed.
5. Dry-run a follow-up example.

Pseudocode

base_pattern_state
extra_state_from_followup
process in valid order
relax/update answer
return final state
  

Sample Dry Run

Use one small BFS/DFS Island Family sample and explicitly track the extra state introduced by the follow-up.

Edge Cases

• Disconnected/unreachable state
• Cycles or repeated states
• Large constraints
• Tie-breaking

Common Mistakes

• Forcing the base template without adding required state
• Not proving why revisits are safe or unsafe
• Missing cycle handling

Complexity

Java, C++ and Python Notes

• Java: prefer explicit classes and clear helper methods over clever one-liners.
• C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
• Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

• Name the pattern before coding.
• State the invariant or DP state in one sentence.
• Dry-run the smallest non-trivial example.
• Close with time and space complexity.