PracHub
QuestionsCoachesLearningGuidesInterview Prep

Quick Overview

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.

  • Medium
  • Apple
  • Coding & Algorithms
  • Software Engineer

Implement DFS for connected components

Company: Apple

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: Medium

Interview Round: Onsite

Given an undirected graph with n nodes (1 ≤ n ≤ 200, 000) and an edge list, implement depth-first search to compute (a) the number of connected components and (b) the size of the largest component; provide both recursive and iterative implementations; discuss stack-safety for large graphs, time and space complexity, and how you would test edge cases.

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.

You are given an undirected graph with `n` nodes labeled from `1` to `n`, and a list of edges where each edge `[a, b]` connects node `a` and node `b`. Using depth-first search, compute two values: - **(a)** the number of connected components in the graph, and - **(b)** the size (number of nodes) of the largest connected component. Return the answer as an array of exactly two integers: `[number_of_components, size_of_largest_component]`. A connected component is a maximal set of nodes such that there is a path between any two nodes in the set. An isolated node (one with no edges) is itself a connected component of size 1. **Example:** ``` n = 5, edges = [[1,2],[2,3],[4,5]] ``` Components are `{1,2,3}` (size 3) and `{4,5}` (size 2), so the answer is `[2, 3]`. Implement DFS to traverse each component. An iterative (explicit-stack) DFS is preferred over a recursive one here because `n` can be as large as 200,000 and a deep chain would overflow the call stack — the reference solution below uses the iterative form for stack safety.

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

  1. Build an adjacency list from the edge list so you can traverse each node's neighbors in O(1) amortized time.
  2. 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.
  3. Track the size of each component as you traverse, and keep a running maximum for the largest-component answer.
  4. 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.
Last updated: Jun 26, 2026

Loading coding console...

PracHub

Master your tech interviews with 8,000+ real questions from top companies.

Product

  • Questions
  • Learning Tracks
  • Interview Guides
  • Resources
  • Premium
  • For Universities
  • Student Access

Browse

  • By Company
  • By Role
  • By Category
  • Topic Hubs
  • SQL Questions
  • AI Coding Questions
  • Compare Platforms
  • Discord Community

Support

  • support@prachub.com
  • (916) 541-4762

Legal

  • Privacy Policy
  • Terms of Service
  • About Us

© 2026 PracHub. All rights reserved.

Related Coding Questions

  • Minimum Cells to Bridge a Magic Grid - Apple (hard)
  • Find Common Prefix Across Strings - Apple (easy)
  • Find Minimum Processing Rate - Apple
  • Compute Earliest Bus Arrival - Apple (medium)
  • Find the Extra Edge - Apple (hard)