FastPrep
Problem · Graph

Minimum Connection Changes

Learn this problem
● MediumInMobi logoInMobiNEW GRADOA

Problem statement

There are n computers labeled from 1 through n. The array connections describes undirected wires, where connections[i] = [a, b] means computers a and b are directly connected.

In one operation, you may remove one existing wire and reconnect that same wire between any two computers. Return the minimum number of operations needed to make every computer reachable from every other computer. Return -1 when this is impossible.

The input contains no self-connections and no duplicate wires.

Function

minimumConnectionChanges(n: int, connections: int[][]) → int

Examples

Example 1

n = 4connections = [[1,2],[1,3],[2,3]]return = 1

Computers 1, 2, and 3 already contain a redundant wire. Move one such wire to connect computer 4 to that component.

Example 2

n = 4connections = [[1,2],[3,4]]return = -1

Connecting four computers requires at least three wires, but only two are available.

Example 3

n = 6connections = [[1,2],[1,3],[1,4],[2,3],[2,4]]return = 2

The component containing computers 1 through 4 has two redundant wires. Move those two wires to attach computers 5 and 6.

Constraints

  • 1 ≤ n ≤ 10^5
  • 0 ≤ connections.length ≤ min(10^5, n × (n - 1) / 2)
  • connections[i].length = 2
  • 1 ≤ connections[i][0], connections[i][1] ≤ n
  • connections[i][0] ≠ connections[i][1]
  • No two entries describe the same undirected wire.

More InMobi problems

drafts saved locally
public int minimumConnectionChanges(int n, int[][] connections) {
  // write your code here
}
n4
connections[[1,2],[1,3],[2,3]]
expected1
checking account