Connecting Cities With Minimum Cost

Connecting Cities With Minimum Cost 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.

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

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:

Preparing this workspace.