Who Connects Each Village to the Cable Network
Solve this ProblemA cable company connects n villages, starting from village 0. All possible cables have different costs, so the cheapest way to connect every village is a single, unique network (a tree). For each village, report which village it is attached to on the way back to village 0 in that network (its parent), using -1 for village 0 itself.
Prim's algorithm builds exactly this tree: it repeatedly attaches the unconnected village that is cheapest to reach, and the village it was attached from is its parent.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 7 villages numbered 0 … n-1; weights is a symmetric n × n matrix: weights[u][v] = 0 means no cable is possible between u and v, otherwise weights[u][v] (1 … 30) is its cost - ◆
All cable costs in the matrix are DISTINCT, so the cheapest network (minimum spanning tree) is unique - ◆
The network is grown from village 0. The parent of a village is the village it is connected to on the way to village 0 in the cheapest network - ◆
Return an array parent where parent[0] = -1 and parent[i] is the parent of village i (a village that cannot be connected to 0 also gets -1)
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Prim by Scanning Every Cable Each Time
BruteGrow the network from village 0. In each of the n − 1 steps, scan every pair (u, v) with u already connected and v not yet connected, and pick the cheapest cable among all of them; connect v and record u as its parent. The cheapest cable leaving the connected part is always part of the cheapest network (cut property). Each step examines all n² pairs, so it takes O(n³) with a matrix.
O(n³)O(n)1class Solution {
2 public int[] treeParents(int[][] weights) {
3 int n = weights.length;
4 int INF = Integer.MAX_VALUE;
5 boolean[] inTree = new boolean[n];
6 int[] parent = new int[n];
7 Arrays.fill(parent, -1);
8 inTree[0] = true;
9 for (int step = 1; step < n; step++) {
10 int bestWeight = INF, from = -1, to = -1;
11 for (int u = 0; u < n; u++) {
12 if (!inTree[u]) continue;
13 for (int v = 0; v < n; v++) {
14 if (!inTree[v] && weights[u][v] > 0 && weights[u][v] < bestWeight) {
15 bestWeight = weights[u][v];
16 from = u;
17 to = v;
18 }
19 }
20 }
21 if (from == -1) break;
22 inTree[to] = true;
23 parent[to] = from;
24 }
25 return parent;
26 }
27}Optimal — Prim’s Algorithm With key[] and parent[]
OptimalInstead of rescanning all cables every time, remember for every unconnected village the cheapest cable found so far to the connected part (key) and the village at its other end (parent). Repeatedly connect the unconnected village with the smallest key, then look only at the cables of that village: if one of them is cheaper than a neighbour's key, update that neighbour's key and parent. Each round costs O(n), for O(n²) in total (O(E log n) with a heap).
O(n²)O(n)1class Solution {
2 public int[] treeParents(int[][] weights) {
3 int n = weights.length;
4 int INF = Integer.MAX_VALUE;
5 boolean[] inTree = new boolean[n];
6 int[] key = new int[n];
7 int[] parent = new int[n];
8 Arrays.fill(key, INF);
9 Arrays.fill(parent, -1);
10 key[0] = 0;
11 for (int round = 0; round < n; round++) {
12 int u = -1;
13 for (int i = 0; i < n; i++) {
14 if (!inTree[i] && (u == -1 || key[i] < key[u])) u = i;
15 }
16 if (key[u] == INF) break;
17 inTree[u] = true;
18 for (int v = 0; v < n; v++) {
19 if (weights[u][v] > 0 && !inTree[v] && weights[u][v] < key[v]) {
20 key[v] = weights[u][v];
21 parent[v] = u;
22 }
23 }
24 }
25 return parent;
26 }
27}