Optimize Water Distribution in a Village - Practice Coding Problems

Optimize Water Distribution in a Village - Problem

You are tasked with designing an optimal water distribution system for a village with n houses. To ensure every house has access to water, you have two options for each house:

Build a well directly inside the house at cost wells[i-1] for house i
Connect to another well via pipes with costs specified in the pipes array

The pipes array contains entries [house1, house2, cost] representing the cost to connect two houses bidirectionally. Multiple connections between the same houses are possible with different costs.

Goal: Find the minimum total cost to supply water to all houses in the village.

This is a classic Minimum Spanning Tree problem with a twist - we can add virtual wells!

Input & Output

example_1.py — Basic village with 3 houses

$ Input: n = 3, wells = [1, 2, 2], pipes = [[1, 2, 1], [2, 3, 1]]

› Output: 3

💡 Note: Optimal: Build well at house 1 (cost 1), connect house 2 to house 1 via pipe (cost 1), connect house 3 to house 2 via pipe (cost 1). Total cost = 1 + 1 + 1 = 3.

example_2.py — Expensive pipes scenario

$ Input: n = 2, wells = [1, 1], pipes = [[1, 2, 2]]

› Output: 2

💡 Note: Building wells in both houses costs 1 + 1 = 2, while connecting via pipe would cost min(1) + 2 = 3. Better to build individual wells.

example_3.py — Large village optimization

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

› Output: 7

💡 Note: Build well at house 1 (cost 3), connect houses 2, 3, 4 via minimum cost pipes: 1-2 (cost 2), 1-3 (cost 2). Total = 3 + 2 + 2 = 7.

Constraints

1 ≤ n ≤ 10⁴
wells.length == n
0 ≤ pipes.length ≤ 3 × 10⁴
pipes[j].length == 3
1 ≤ wells[i] ≤ 10⁵
1 ≤ pipes[j][0], pipes[j][1] ≤ n
0 ≤ pipes[j][2] ≤ 10⁵
pipes[j][0] ≠ pipes[j][1]

Asked in

The optimal solution uses Minimum Spanning Tree with Virtual Source. By adding a virtual source connected to all houses with well costs as edge weights, we transform the problem into finding the MST using Kruskal's algorithm with Union-Find. This elegant approach achieves O((m+n) log(m+n)) time complexity and guarantees the minimum cost water distribution.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force (Try All Combinations)	O(2^n × n²)	O(n)	Try all possible combinations of wells and pipe connections
Minimum Spanning Tree with Virtual Source (Optimal)	O((m+n) log(m+n))	O(m+n)	Transform to MST problem by adding virtual source connected to all houses with well costs

Brute Force (Try All Combinations) — Algorithm Steps

Generate all possible subsets of houses that could have wells
For each subset, calculate the cost of wells
For remaining houses, find minimum cost to connect to houses with wells
Use BFS/DFS to ensure all houses are reachable
Return the minimum total cost across all valid configurations

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Well Combinations

Try all 2^n possible subsets of houses that could have wells

Calculate Well Costs

Sum up the cost of building wells in selected houses

Find Minimum Spanning Tree

Connect remaining houses using minimum cost pipes

Verify Connectivity

Ensure all houses are connected to water supply

Track Minimum

Keep track of the configuration with minimum total cost

Code -

solution.c — C

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

typedef struct {
    int cost, h1, h2;
} Edge;

int compare(const void *a, const void *b) {
    return ((Edge*)a)->cost - ((Edge*)b)->cost;
}

int find(int parent[], int x) {
    if (parent[x] != x) {
        parent[x] = find(parent, parent[x]);
    }
    return parent[x];
}

int unite(int parent[], int x, int y) {
    int px = find(parent, x), py = find(parent, y);
    if (px != py) {
        parent[px] = py;
        return 1;
    }
    return 0;
}

int minCostToSupplyWater(int n, int* wells, int wellsSize, int** pipes, int pipesSize, int* pipesColSize) {
    int minCost = INT_MAX;
    
    // Try all possible combinations of wells
    for (int wellMask = 1; wellMask < (1 << n); wellMask++) {
        int cost = 0;
        int hasWell[n + 1];
        memset(hasWell, 0, sizeof(hasWell));
        
        // Add cost of wells
        for (int i = 0; i < n; i++) {
            if (wellMask & (1 << i)) {
                cost += wells[i];
                hasWell[i + 1] = 1;
            }
        }
        
        // Union-Find initialization
        int parent[n + 1];
        for (int i = 0; i <= n; i++) {
            parent[i] = i;
        }
        
        // Connect houses with wells
        int wellHouses[n];
        int wellCount = 0;
        for (int i = 1; i <= n; i++) {
            if (hasWell[i]) {
                wellHouses[wellCount++] = i;
            }
        }
        
        if (wellCount == 0) continue;
        
        for (int i = 1; i < wellCount; i++) {
            unite(parent, wellHouses[0], wellHouses[i]);
        }
        
        // Create edges array
        Edge edges[pipesSize];
        int edgeCount = 0;
        
        // Simple approach: add all pipes (could optimize by removing duplicates)
        for (int i = 0; i < pipesSize; i++) {
            edges[edgeCount].cost = pipes[i][2];
            edges[edgeCount].h1 = pipes[i][0];
            edges[edgeCount].h2 = pipes[i][1];
            edgeCount++;
        }
        
        qsort(edges, edgeCount, sizeof(Edge), compare);
        
        int totalPipeCost = 0;
        for (int i = 0; i < edgeCount; i++) {
            if (unite(parent, edges[i].h1, edges[i].h2)) {
                totalPipeCost += edges[i].cost;
            }
        }
        
        // Check connectivity
        int root = find(parent, 1);
        int allConnected = 1;
        for (int i = 2; i <= n; i++) {
            if (find(parent, i) != root) {
                allConnected = 0;
                break;
            }
        }
        
        if (allConnected) {
            int totalCost = cost + totalPipeCost;
            if (totalCost < minCost) {
                minCost = totalCost;
            }
        }
    }
    
    return minCost;
}

Time & Space Complexity

Time Complexity

⏱️

O(2^n × n²)

2^n subsets to try, each requiring O(n²) to check connectivity and find minimum spanning tree

⚠ Quadratic Growth

Space Complexity

O(n)

Space for storing current configuration and visited nodes during connectivity checks

⚡ Linearithmic Space

25.0K Views

Medium Frequency

~15 min Avg. Time

850 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