Prep plan

DFS-BFS vs Union Find

DFS/BFS vs Union Find — Interview Notes

Core Difference

TechniqueBest For
DFS/BFSReachability / Traversal
Union Find (DSU)Grouping / Connectivity

DFS/BFS Mindset

Question:

"What can I reach?"

Use for:

  • Matrix/grid traversal
  • Flood fill
  • Path existence
  • Neighbor exploration

Examples:

  • Number of Islands
  • Rotten Oranges
  • Word Search

Typical pattern:

Start from one cell/node
→ explore neighbors
→ mark visited

Union Find Mindset

Question:

"What belongs together?"

Use for:

  • Connected components
  • Dynamic connectivity
  • Merging groups
  • Cycle detection

Examples:

  • Number of Connected Components
  • Accounts Merge
  • Redundant Connection

Typical pattern:

union(a, b)

Meaning:

a and b are in same group

Important Interview Insight

Number of Connected Components

Usually:

  • DFS/BFS OR
  • Union Find

But Union Find feels natural because:

  • edges are explicitly given

Number of Islands

Usually:

  • DFS/BFS

Because:

  • matrix traversal is spatial
  • neighbors are implicit

Heuristic

Problem ShapeFirst Thought
Grid / MatrixDFS/BFS
Explicit edgesUnion Find possible
Dynamic connectionsUnion Find
Flood fillDFS/BFS

Final Rule

DFS/BFS → traversal
Union Find → grouping