Connecting Cities With Minimum Cost

Connecting Cities With Minimum Cost

What is this problem about?

The Connecting Cities With Minimum Cost interview question is a classic graph optimization problem. Imagine you are given N cities, and some cities can be connected with roads. Each connection has a specific cost associated with it. The goal is to find the minimum total cost to connect all cities such that every city is reachable from every other city (either directly or indirectly). If it is impossible to connect all cities, you must return -1. This is a direct application of finding a Minimum Spanning Tree (MST) in a graph.

Why is this asked in interviews?

Amazon and other logistics-heavy companies frequently ask the Connecting Cities With Minimum Cost coding problem because it mirrors real-world infrastructure planning. It tests a candidate's ability to model problems using graphs and their understanding of greedy algorithms. Interviewers want to see if you can efficiently handle connectivity and cycle detection in a network.

Algorithmic pattern used

This problem primarily uses the Union Find, Graph, Heap (Priority Queue), Minimum Spanning Tree interview pattern. There are two standard algorithms to solve this:

1. Kruskal's Algorithm: Sort all potential roads by cost and use a Union-Find data structure to add roads that connect different components without forming cycles.
2. Prim's Algorithm: Start from an arbitrary city and use a Priority Queue (Min-Heap) to always pick the cheapest road that connects a new city to the already connected group.

Example explanation

Suppose we have 3 cities (1, 2, 3) and roads:

• Road (1, 2) cost 5
• Road (1, 3) cost 6
• Road (2, 3) cost 1

Using a greedy approach (Kruskal's):

1. Pick the cheapest road: (2, 3) with cost 1. Cities 2 and 3 are now connected.
2. Pick the next cheapest: (1, 2) with cost 5. Now City 1 is connected to the (2, 3) group.
3. All cities are connected. Total cost = 1 + 5 = 6.
4. Even though road (1, 3) exists, adding it would form a cycle and increase the cost unnecessarily.

Common mistakes candidates make

• Not checking connectivity: Forgetting to verify if all cities are actually connected at the end. If you have 10 cities but only 8 roads in your MST, the graph is disconnected.
• Using BFS/DFS: While these can check connectivity, they aren't designed to find the minimum cost for connections.
• Inefficient sorting: Not using a Priority Queue or sorting properly, leading to higher time complexity.

Interview preparation tip

Master the Union-Find data structure with path compression and union by rank. It is one of the most powerful tools for solving connectivity and grouping problems efficiently in a coding interview.