Optimize Water Distribution in a Village

Explore Solutions in Other Languages

Code Solution


class Solution {
  public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
    int ans = 0;
    List>[] graph = new List[n + 1];
    Queue> minHeap =
        new PriorityQueue<>(Comparator.comparing(Pair::getKey)); // (d, u)

    for (int i = 0; i <= n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] pipe : pipes) {
      final int u = pipe[0];
      final int v = pipe[1];
      final int w = pipe[2];
      graph[u].add(new Pair<>(v, w));
      graph[v].add(new Pair<>(u, w));
    }

    // Connect virtual 0 with nodes 1 to n.
    for (int i = 0; i < n; ++i) {
      graph[0].add(new Pair<>(i + 1, wells[i]));
      minHeap.offer(new Pair<>(wells[i], i + 1));
    }

    Set mst = new HashSet<>(Arrays.asList(0));

    while (mst.size() < n + 1) {
      Pair pair = minHeap.poll();
      final int d = pair.getKey();
      final int u = pair.getValue();
      if (mst.contains(u))
        continue;
      // Add the new vertex.
      mst.add(u);
      ans += d;
      // Expand if possible.
      for (Pair pair : graph[u]) {
        final int v = pair.getKey();
        final int w = pair.getValue();
        if (!mst.contains(v))
          minHeap.offer(new Pair<>(w, v));
      }
    }

    return ans;
  }
}

Problem Description

Imagine a village where the only thing more scarce than water is a good Wi-Fi connection. The villagers are tired of carrying buckets from the nearest well, and you, the benevolent overlord, have decided to help them out. The problem is, you need to do it in the most cost-effective way possible.

You have n houses and a list of wells, each with a specific cost to dig. Additionally, there are pipes that can connect the houses, each with its own installation cost. Your mission is to minimize the total cost of supplying water to all houses.

Approach

The solution employs a graph-based approach using Prim’s algorithm to find the Minimum Spanning Tree (MST). The algorithm starts by connecting a virtual node (representing the wells) to the houses and then expands the tree by adding the cheapest connection available until all houses are connected.

Graph Representation: The houses and pipes are represented as a graph where nodes are houses and edges are the costs of pipes or wells.
Priority Queue: A min-heap (priority queue) is used to always expand the least costly edge first.
MST Construction: The algorithm continues until all houses are connected, ensuring the minimum cost is achieved.

Time and Space Complexity

Complexity Type	Complexity
Time Complexity	O((n + m) log n)
Space Complexity	O(n + m)

Real-World Example

Imagine you are the mayor of a small village. The villagers are tired of walking miles to fetch water, and you have a budget to either dig wells or lay down pipes. You need to decide the best way to ensure every house has access to water without breaking the bank. By applying the above algorithm, you can determine the most cost-effective way to supply water, ensuring that every villager can quench their thirst without emptying their wallets.