How should I practice Minimum Edges to Connect All Components?

Start by reading the full statement, solve the visible examples, then compare the pattern against related InMobi onsite interview problems in FastPrep.

Is Minimum Edges to Connect All Components associated with InMobi?

FastPrep tags this as a InMobi onsite interview coding practice problem when the problem catalog has that company and stage context.

Problem · Graph

Minimum Edges to Connect All Components

Learn this problem

● Easy

InMobiFULLTIMEONSITE INTERVIEW

Problem statement

A country has n cities numbered from 0 through n - 1. The array edges describes existing undirected roads, where each pair [u, v] connects cities u and v.

You may add a road between any two different cities. Return the minimum number of new roads needed so that every city is reachable from every other city.

If the current graph has k connected components, joining those components requires exactly k - 1 new roads.

Function

minEdgesToConnect(n: int, edges: int[][]) → int

Examples

Example 1

n = 4edges = [[0,1],[2,3]]return = 1

The graph has two connected components. One new road between them makes the whole country connected.

Example 2

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

Cities 0, 1, and 2 form one component, while cities 3 and 4 form another.

Example 3

n = 4edges = []return = 3

Every city starts as its own component, so connecting four components needs three new roads.

Constraints

1 ≤ n ≤ 100,000
0 ≤ edges.length ≤ 200,000
edges[i].length = 2
0 ≤ edges[i][0], edges[i][1] < n
Every existing edge connects two different cities.