Coupang Coding Interview: Connected Components (Graph)

You are given n nodes (0 to n-1) and a list of undirected edges. Your task is to return the number of connected components in the graph. In an interview you'll be expected to clarify assumptions (are there duplicate edges? self-loops? constraints on n and edges?) and pick an approach that matches the input size and required complexity.

Start by explaining high-level options: perform graph traversal (BFS or DFS) to mark visited nodes and count how many times you start a new traversal, or use a Union-Find (disjoint set) structure to union endpoints and then count distinct roots. Walk through one approach on a small example to show correctness (e.g., edges [[0,1],[1,2],[3,4]] gives 2 components).

Typical interview flow:

• Clarify input format and edge cases (isolated nodes, no edges).
• Choose and justify an algorithm (BFS/DFS vs Union-Find) given constraints.
• Implement and test on examples, then discuss time/space trade-offs.

Skill signals you should demonstrate:

• Correctness and handling of edge cases (isolated vertices, repeated edges).
• Ability to implement iterative DFS/BFS or Union-Find with path compression/rank.
• Complexity analysis: DFS/BFS O(n + m) time and O(n + m) space; Union-Find approximately O((n + m) α(n)) time and O(n) space.

Prepare to explain why you chose an approach, show how you'd extend it (component sizes, dynamic edge updates), and discuss performance at scale.