Implement DFS for connected components
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Quick Answer: This question evaluates a candidate's ability to implement depth-first search for connected components, covering both recursive and iterative implementations while testing understanding of stack-safety, time and space complexity, and edge-case testing.
Constraints
- 1 <= n <= 200,000
- 0 <= number of edges <= n * (n - 1) / 2
- Nodes are labeled from 1 to n (1-indexed).
- Edges are undirected; edge [a, b] is the same as [b, a].
- The graph may contain isolated nodes (counted as components of size 1).
- Return [number_of_components, size_of_largest_component].
Examples
Input: (5, [[1, 2], [2, 3], [4, 5]])
Expected Output: [2, 3]
Explanation: Components {1,2,3} (size 3) and {4,5} (size 2). Two components; the largest has 3 nodes.
Input: (1, [])
Expected Output: [1, 1]
Explanation: A single isolated node is one component of size 1.
Input: (4, [])
Expected Output: [4, 1]
Explanation: Four isolated nodes with no edges form four components, each of size 1.
Input: (6, [[1, 2], [2, 3], [3, 1], [4, 5]])
Expected Output: [3, 3]
Explanation: Components: triangle {1,2,3} (size 3), edge {4,5} (size 2), and isolated node {6} (size 1). Three components; largest is size 3.
Input: (7, [[1, 2], [3, 4], [4, 5], [5, 6], [6, 7]])
Expected Output: [2, 5]
Explanation: Components {1,2} (size 2) and the chain {3,4,5,6,7} (size 5). Two components; largest is size 5.
Input: (3, [[1, 2], [2, 3], [1, 3]])
Expected Output: [1, 3]
Explanation: All three nodes form a single fully connected component of size 3.
Hints
- Build an adjacency list from the edge list so you can traverse each node's neighbors in O(1) amortized time.
- Keep a `visited` array. Iterate over every node 1..n; each time you reach an unvisited node, that's a new component — run a DFS from it and count how many nodes it reaches.
- Track the size of each component as you traverse, and keep a running maximum for the largest-component answer.
- Prefer an iterative DFS with an explicit stack over recursion: with n up to 200,000, a long path would overflow the recursion call stack.