FastPrep
Problem

Minimum Spanning Tree Weight in a Complete Binary Graph

Learn this problem
Uber logoUberFULLTIMEOA
See Uber hiring insights

Problem statement

You are given n nodes in a complete undirected graph. Some edges have weight 1; every other edge has weight 0. The weight-1 edges are given in the array oneEdges, where each edge is represented as [u, v].

Return the total weight of a minimum spanning tree of this complete graph.

Function

minimumSpanningTreeWeight(n: int, oneEdges: int[][]) → int

Examples

Example 1

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

All edges not listed in oneEdges have weight 0. The zero-weight edges can connect all four nodes, so the MST weight is 0.

Example 2

n = 3oneEdges = [[1, 2], [1, 3], [2, 3]]return = 2

Every edge has weight 1, so any spanning tree uses two weight-1 edges.

Constraints

  • 1 <= n <= 2 * 10^5
  • 0 <= oneEdges.length <= min(n * (n - 1) / 2, 2 * 10^5)
  • 1 <= u < v <= n for each edge in oneEdges
  • oneEdges contains no duplicate edges.

More Uber problems

drafts saved locally
public int minimumSpanningTreeWeight(int n, int[][] oneEdges) {
  // write your code here
}
n4
oneEdges[[1, 2], [2, 3], [3, 4]]
expected0
checking account