Cheapest way to cable every office together

Graphs Senior Python 3.13+ Reviewed By Best Latest Apps

Order the steps

Put Kruskal's algorithm in order.

  • Give every office its own group
  • Sort all cables by cost
  • Stop after n - 1 cables, or report -1 if you run out first
  • For each cable, take it if its two offices are in different groups, and join the groups

Choose an answer, then open Show answer below to check it.

Show answer

Answer: B A D C

  1. Sort all cables by cost Cheap cables are considered first.
  2. Give every office its own group Union-find starts with n separate groups.
  3. For each cable, take it if its two offices are in different groups, and join the groups Cables inside a group would only make a loop.
  4. Stop after n - 1 cables, or report -1 if you run out first A tree on n offices has n - 1 edges.

30-second answer

Kruskal's algorithm: sort cables by cost and take each one that joins two offices not yet connected (union-find tells you). Stop after n - 1 cables. The result is a minimum spanning tree. O(E log E) for the sort, and O(V + E) space for the sorted cables and the union-find array.

Practise saying it · 60 s. No recording, just a timer

Explain Kruskal's minimum spanning tree.

Say your answer out loud, then check which of these points you covered:

  • Sort by cost
  • Union-find to skip loops
  • n - 1 edges or -1

Deep dive

The 'cut property' makes greedy safe: the cheapest cable crossing any split of the offices belongs to some cheapest network.

Prim's algorithm grows one tree from a start office with a heap: O(E log V), and its array version suits dense graphs given as matrices.

Fewer than n - 1 cables taken means the offices cannot all be connected.

Python solution Ran on Python 3.13.5 · mypy --strict
Python 3.13
def cheapest_cabling(n: int, cables: list[list[int]]) -> int:
    boss = list(range(n))

    def find(x: int) -> int:
        while boss[x] != x:
            boss[x] = boss[boss[x]]
            x = boss[x]
        return x

    total = used = 0
    for a, b, cost in sorted(cables, key=lambda e: e[2]):
        ra, rb = find(a), find(b)
        if ra != rb:
            boss[ra] = rb
            total += cost
            used += 1
    return total if used == n - 1 else -1

Common mistakes

  • Taking the cheapest cable at each office independently, which can leave the network split.
  • Forgetting the -1 case for disconnected input.

Senior take & follow-ups

Name the cut property. It is the one-line proof that greedy works here.

Follow-up questions

Think of your answer first, then open the hint.

  1. What if a cable must be included?

    Show hint

    Take it first, then run Kruskal on the rest.

  2. How do you find the second-cheapest network?

    Show hint

    Try removing each tree cable and rebuilding, or use path maximum queries.

What each operation costs: Breadth First Search · Depth First Search · Topological Sort · Dijkstra Algorithm

From the author

DSA Master - Data & Algorithms

Free on iPhone and iPad: watch 50+ data structures and algorithms step through animations, run the code in the playground, and try the daily challenge.

Get it on the App Store

Suggest a fix if something here is wrong or out of date.