FastPrepCount Connected Components in an Undirected Graph
Problems/Count Connected Components in an Undirected Graph

Count Connected Components in an Undirected Graph

Nutanix logoNutanix● MediumINTERNONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: Reported in a 2025 Nutanix campus internship loop. The manager round mixed operating-system questions with one coding task: count how many connected components a graph has.

That is all the report gives. It does not describe the graph or its input, and it has no examples or limits. Here the graph is undirected and its nodes are 0 to n - 1. It comes as a list of edges with no self-loops or repeated edges. A node with no edges counts as its own component. The size limits are our choices.

Our version is about 85% the same as the reported question.

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[][]) → int

Examples

Example 1

n = 6edges = [[0,3],[3,5],[1,4]]return = 3

Nodes 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 = 1

The 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 = 3

There are no edges, so each of the three nodes is its own component.

Constraints

  • 1 <= n <= 10^4
  • 0 <= edges.length <= 2 * 10^4
  • edges[i].length == 2
  • 0 <= edges[i][0], edges[i][1] <= n - 1
  • edges[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

Interview reports that mention this question

  • Nutanix Intern Debugging Round and Interviews: 25 Experiences

Nutanix interview experiences

  • Nutanix SWE Intern Phone Screens: 20 Experiences (Part 3 of 3)
  • Nutanix SWE Intern OA Questions: 16 Experiences (Part 2 of 3)
  • Nutanix U.S. SWE Intern Interviews: 54 Experiences (Part 1 of 3)
  • Nutanix SWE OA and Interviews, Level Not Reported: 9 Experiences
All Nutanix interview questionsSee Nutanix hiring insights
Saved
class Solution {
    public int countComponents(int n, int[][] edges) {
        // Write your code here.
    }
}
Checking account…