Minimum Connection Cost

Connecting Cities With Minimum Cost (LeetCode 1135)
This Amazon interview problem involves finding the minimum cost to connect n cities using given bidirectional connections, ensuring all cities form a single connected component. It's commonly tagged with Array (for connection lists), Greedy (via Kruskal's algorithm), and Graph/Union-Find, though Binary Search isn't a primary tag—some variations may use it for optimization.[1][3]

Full Problem Statement

Given an integer n representing the number of cities (numbered from 1 to n) and a list of connections where connections[i] = [city1i, city2i, costi] indicates an undirected edge between city1i and city2i with cost costi, return the minimum total cost to connect all n cities such that every pair of cities is connected via some path. If impossible, return -1.[3]

Input/Output Examples

Example 1

Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]
Output: 6
Explanation: Connect 1-2 (cost 5) and 2-3 (cost 1); total 6. City 1 reaches 3 via 2, avoiding the direct 1-3 edge.[3]

Example 2

Input: n = 4, connections = [[1,2,3],[3,4,5]]
Output: -1
Explanation: Only 2 edges for 4 cities; cannot connect all (need at least 3 edges for a tree).[1]

Example 3 (from discussions)

Input: n = 6, connections = [[1,4,5],[1,2,5],[1,6,2],[2,6,4],[3,4,3],[3,6,1]] (approximate)
Output: 7 (e.g., connect components via cheapest edges like 1-6 and 1-2).[10]

Constraints

• 1 <= n <= 10^4
• 0 <= connections.length <= 10^4
• 1 <= city1i ≠ city2i <= n
• 1 <= costi <= 10^5
• Each connection is unique (no duplicate edges).[3]