Connecting Cities With Minimum Cost - Practice Coding Problems

Connecting Cities With Minimum Cost - Problem

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

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.

Input & Output

Example 1 — Basic Connected Graph

$ Input: n = 3, connections = [[1,2,5],[1,3,6],[2,3,1]]

› Output: 6

💡 Note: We need to connect all 3 cities. The minimum spanning tree uses edges [2,3,1] and [1,2,5], giving total cost 1 + 5 = 6.

Example 2 — Impossible to Connect

$ Input: n = 4, connections = [[1,2,3],[3,4,4]]

› Output: -1

💡 Note: Cities 1,2 form one component and cities 3,4 form another component. There's no way to connect them since no connection exists between the components.

Example 3 — Single City

$ Input: n = 1, connections = []

› Output: 0

💡 Note: Only one city exists, so no connections are needed. The cost is 0.

Constraints

1 ≤ n ≤ 10⁴
0 ≤ connections.length ≤ 10⁴
connections[i].length == 3
1 ≤ xi, yi ≤ n
xi ≠ yi
0 ≤ costi ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Cities

n cities and possible connections with costs

Build MST

Use Kruskal's algorithm to find minimum spanning tree

Output Cost

Return total cost of MST, or -1 if impossible

Key Takeaway

🎯 Key Insight: Use Kruskal's algorithm with Union-Find to greedily build minimum spanning tree

Asked in

G Google 42 a Amazon 38 F Facebook 35 M Microsoft 31

This is a classic Minimum Spanning Tree (MST) problem. The optimal approach uses Kruskal's algorithm with Union-Find: sort connections by cost, then greedily add the cheapest connections that don't create cycles. Time: O(m log m), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Try All Subsets	O(2^m × n)	O(n)	Check every possible subset of connections to find minimum cost spanning tree
Kruskal's Algorithm with Union-Find	O(m log m)	O(n)	Sort connections by cost and greedily add edges using Union-Find to avoid cycles

Brute Force - Try All Subsets — Algorithm Steps

Generate all 2^m subsets of connections
For each subset, check if it connects all n cities
Calculate cost and track minimum

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Subsets

Create all 2^m possible connection combinations

Check Connectivity

Use Union-Find to verify if subset connects all cities

Track Minimum

Keep track of minimum cost among valid subsets

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

typedef struct {
    int *parent;
    int components;
} UnionFind;

UnionFind* createUF(int n) {
    UnionFind* uf = malloc(sizeof(UnionFind));
    uf->parent = malloc((n + 1) * sizeof(int));
    uf->components = n;
    for (int i = 0; i <= n; i++) {
        uf->parent[i] = i;
    }
    return uf;
}

int find(UnionFind* uf, int x) {
    if (uf->parent[x] != x) {
        uf->parent[x] = find(uf, uf->parent[x]);
    }
    return uf->parent[x];
}

int unite(UnionFind* uf, int x, int y) {
    int px = find(uf, x);
    int py = find(uf, y);
    if (px != py) {
        uf->parent[px] = py;
        uf->components--;
        return 1;
    }
    return 0;
}

int isConnected(int n, int connections[][3], int count) {
    UnionFind* uf = createUF(n);
    for (int i = 0; i < count; i++) {
        unite(uf, connections[i][0], connections[i][1]);
    }
    int result = (uf->components == 1);
    free(uf->parent);
    free(uf);
    return result;
}

int solution(int n, int connections[][3], int m) {
    if (m == 0) {
        return n > 1 ? -1 : 0;
    }
    
    int minCost = INT_MAX;
    
    // Try all possible subsets
    for (int mask = 1; mask < (1 << m); mask++) {
        int subset[100][3];
        int count = 0;
        int cost = 0;
        
        for (int i = 0; i < m; i++) {
            if (mask & (1 << i)) {
                subset[count][0] = connections[i][0];
                subset[count][1] = connections[i][1];
                subset[count][2] = connections[i][2];
                cost += connections[i][2];
                count++;
            }
        }
        
        if (isConnected(n, subset, count)) {
            if (cost < minCost) {
                minCost = cost;
            }
        }
    }
    
    return minCost == INT_MAX ? -1 : minCost;
}

int main() {
    int n;
    scanf("%d", &n);
    
    char line[1000];
    scanf(" %[^\n]", line);
    
    int connections[100][3];
    int m = 0;
    
    // Simple parsing for [[a,b,c],[d,e,f],...]
    char* ptr = line + 1; // Skip first [
    while (*ptr && *ptr != ']') {
        if (*ptr == '[') {
            ptr++;
            connections[m][0] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            connections[m][1] = atoi(ptr);
            while (*ptr && *ptr != ',') ptr++;
            ptr++;
            connections[m][2] = atoi(ptr);
            while (*ptr && *ptr != ']') ptr++;
            ptr++;
            m++;
        } else {
            ptr++;
        }
    }
    
    printf("%d\n", solution(n, connections, m));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^m × n)

2^m subsets to check, each requiring O(n) connectivity verification

✓ Linear Growth

Space Complexity

O(n)

Union-Find structure for connectivity checking

⚡ Linearithmic Space

67.0K Views

High Frequency

~25 min Avg. Time

956 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Try All Subsets — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler