Is Connecting Cities With Minimum Cost easy or hard?

Connecting Cities With Minimum Cost is classified as Medium difficulty. The challenge lies in recognizing it as a Minimum Spanning Tree problem and choosing the correct greedy algorithm such as Kruskal or Prim.

Connecting Cities With Minimum Cost Python/Java solution

Most implementations follow the Kruskal pattern: sort edges by cost, iterate through them, and union cities if they are not already connected. The logic is identical across Python, Java, C++, Go, and TypeScript, differing only in syntax and class structure.

How to solve Connecting Cities With Minimum Cost in O(E log E)?

Use Kruskal's Minimum Spanning Tree algorithm. First sort all connections by cost. Then iterate through them and use a Union Find structure to connect cities if they belong to different components. Stop once exactly n-1 edges are chosen, which forms a spanning tree.

What is the best approach for Connecting Cities With Minimum Cost?

Kruskal's algorithm with a Union Find (Disjoint Set Union) data structure is the most common solution. Sort all edges by cost and add them to the network only if they connect two different components. This guarantees the minimum spanning tree while avoiding cycles. The time complexity is O(E log E) due to sorting.

Is Connecting Cities With Minimum Cost asked at Google/Amazon/Meta?

Minimum Spanning Tree problems like this frequently appear in interviews at companies such as Amazon, Google, and Meta. Variants involving network cost optimization, connecting servers, or building road systems are common graph interview questions.

What data structure is used in Connecting Cities With Minimum Cost?

The optimal approach uses a Union Find (Disjoint Set Union) data structure to track connected components efficiently. Some solutions also use a priority queue (min heap) when implementing Prim's algorithm for the minimum spanning tree.

What is the time complexity of Connecting Cities With Minimum Cost?

The optimal solution using Kruskal's algorithm runs in O(E log E) time where E is the number of connections. Sorting edges dominates the runtime, while union-find operations are nearly constant with path compression. Space complexity is O(V) for the disjoint set structure.

Description Hints 6 Solution Video 9:42

1135. Connecting Cities With Minimum Cost

Medium63.5% acceptance1 companyPremium elsewhere, free here

There are n cities labeled from 1 to n. You are given the integer n and an array connections where connections[i] = [x_i, y_i, cost_i] indicates that the cost of connecting city x_i and city y_i (bidirectional connection) is cost_i.

Return the minimum cost to connect all the n cities such that there is at least one path between each pair of cities. If it is impossible to connect all the n cities, return -1,

The cost is the sum of the connections' costs used.

Example 1:

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Choosing any 2 edges will connect all cities so we choose the minimum 2.

Example 2:

Input: n = 4, connections = [[1,2,3],[3,4,4]]
Output: -1
Explanation: There is no way to connect all cities even if all edges are used.

Constraints:

1 <= n <= 10⁴
1 <= connections.length <= 10⁴
connections[i].length == 3
1 <= x_i, y_i <= n
x_i != y_i
0 <= cost_i <= 10⁵

Asked at 1 company

Amazon

Topics

Graph Heap (Priority Queue)Minimum Spanning Tree Union Find

Hints open one at a time

Hint 1

What if we model the cities as a graph?

Hint 2

Build a graph of cities and find the minimum spanning tree.

Hint 3

You can use a variation of the Kruskal's algorithm for that.

Hint 4

Sort the edges by their cost and use a union-find data structure.

Hint 5

How to check all cities are connected?

Hint 6

At the beginning we have n connected components, each time we connect two components the number of connected components is reduced by one. At the end we should end with only a single component otherwise return -1.

9:42

Still stuck?Read the written solution, or watch a walkthrough.

Open solution