1135. Connecting Cities With Minimum Cost

Connecting Cities With Minimum Cost (LeetCode 1135) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Minimum Spanning Tree (Kruskal / Prim / DSU + heap) subpattern.

How to solve Connecting Cities With Minimum Cost

Connecting Cities With Minimum Cost is a Minimum Spanning Tree problem, part of Graph Traversal Patterns (DFS & BFS). Find minimum spanning tree using Kruskal's or Prim's algorithm with Union-Find or heap.

Work towards the solution in these steps:

1. Think about representing the cities and connections as a graph where nodes are cities and edges are the connections with associated costs.
2. To connect all cities with minimum total cost, consider what type of graph structure ensures all nodes are connected with minimal edge weights.
3. Minimum Spanning Tree (MST) algorithms like Kruskal's or Prim's are designed to find such a minimal set of edges connecting all nodes without cycles.

The reference solution runs in O(nlogn) time and O(n) space.

The Connecting Cities With Minimum Cost solution and editorial walks through the full approach with reference code.

Problem statement

There are N cities numbered from 1 to N.

You are given connections, where each connections[i] = [city1, city2, cost] represents the cost to connect city1 and city2 together. (A connection is bidirectional: connecting city1 and city2 is the same as connecting city2 and city1.) Return the minimum cost so that for every pair of cities, there exists a path of connections (possibly of length 1) that connects those two cities together. The cost is the sum of the connection costs used. If the task is impossible, return -1.

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.

Note:

- 1 <= N <= 10000 - 1 <= connections.length <= 10000 - 1 <= connections[i][0], connections[i][1] <= N - 0 <= connections[i][2] <= 10^5 - connections[i][0] != connections[i][1]

Topics and companies

Topics: Union Find, Graph.

Reported in interviews at Amazon, Uber.

How to practise Connecting Cities With Minimum Cost on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open Connecting Cities With Minimum Cost in the code editor, or read the Connecting Cities With Minimum Cost editorial for a worked solution with its approach and complexity analysis.

Where Connecting Cities With Minimum Cost sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Minimum Spanning Tree (Kruskal / Prim / DSU + heap) subpattern
• The full DSA patterns sheet

Problems related to Connecting Cities With Minimum Cost

Other problems that use the same Minimum Spanning Tree (Kruskal / Prim / DSU + heap) and Graph Traversal Patterns (DFS & BFS) techniques:

• Min Cost to Connect All Points — Medium, same subpattern
• Optimize Water Distribution in a Village — Hard, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• All Paths from Source Lead to Destination — Medium, same pattern
• Build a Matrix With Conditions — Hard, same pattern

Connecting Cities With Minimum Cost FAQ