Count Connected Components in an Undirected Graph
Updated
Problem statement
You are given an undirected graph with n nodes labeled from 0 to n - 1. Each edges[i] = [a, b] joins node a and node b, and you can move along an edge in either direction.
A connected component is a largest group of nodes in which every node can reach every other node by following edges. A node with no edges is a component on its own.
Return the number of connected components in the graph.
Function
countComponents(n: int, edges: int[][]) → intExamples
Example 1
n = 6edges = [[0,3],[3,5],[1,4]]return = 3Nodes 0, 3 and 5 are joined through node 3. Nodes 1 and 4 are joined by one edge. Node 2 has no edges. That makes 3 components.
Example 2
n = 4edges = [[0,1],[1,2],[2,0],[2,3]]return = 1The first three edges form a loop through nodes 0, 1 and 2, and the last edge adds node 3. Every node is reachable from every other node, so there is 1 component. Note that there are 4 edges here, so subtracting the edge count from n would give 0, which is wrong.
Example 3
n = 3edges = []return = 3There are no edges, so each of the three nodes is its own component.
Constraints
1 <= n <= 10^40 <= edges.length <= 2 * 10^4edges[i].length == 20 <= edges[i][0], edges[i][1] <= n - 1edges[i][0] != edges[i][1]- No two edges join the same pair of nodes.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
- Distance Sums to Special Nodes in a Weighted TreeONSITE INTERVIEW · Seen Aug 2021
Similar questions at other companies
- Count Friend CirclesOpenAI · PHONE SCREEN · ONSITE INTERVIEWOpenAI interview questions
- Count Connected Point ClustersGoogle · PHONE SCREEN · ONSITE INTERVIEWGoogle interview questions
- Path Existence in an Undirected GraphBloomberg LP · ONSITE INTERVIEWBloomberg LP interview questions
- Evaluate DivisionApple · PHONE SCREENApple interview questions
- Count the Number of Complete ComponentsAmazon · PHONE SCREEN
- Visible Profiles CountMicrosoft · OAMicrosoft interview questions
- Number of ProvincesSambaNova Systems · PHONE SCREENSambaNova Systems interview questions
- Path Existence in an Undirected GraphByteDance · PHONE SCREENByteDance interview questions
- Connected GroupsVisa · OAVisa interview questions
- Course SchedulePlaud · ONSITE INTERVIEW