LeetCode 1168: Optimize Water Distribution in a Village Solution

Master LeetCode problem 1168 (Optimize Water Distribution in a Village), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

1168. Optimize Water Distribution in a Village

Hard

Union Find Graph Heap (Priority Queue)Minimum Spanning Tree

Problem Explanation

Explanation:

The problem asks us to optimize the water distribution in a village by finding the minimum cost to supply water to all houses. Each house is connected to a central well, and given the connections between houses and the costs of connecting pipes, we need to find the minimum cost to connect all houses with water.

To solve this problem, we can utilize the concept of Minimum Spanning Tree (MST). We can treat each house and the well as nodes in a graph, and each pipe as an edge with a cost. We can then find the MST of this graph to connect all houses with water with minimum cost. We can use Kruskal's algorithm to find the MST efficiently. :

Solution Code

class Solution {
    public int minCostToSupplyWater(int n, int[] wells, int[][] pipes) {
        List<int[]> edges = new ArrayList<>();
        for (int i = 0; i < wells.length; i++) {
            edges.add(new int[]{0, i + 1, wells[i]}); // add edges to wells
        }
        for (int[] pipe : pipes) {
            edges.add(new int[]{pipe[0], pipe[1], pipe[2]});
        }
        
        Collections.sort(edges, (a, b) -> Integer.compare(a[2], b[2])); // sort edges by cost
        
        UnionFind uf = new UnionFind(n + 1); // initialize union find data structure
        
        int cost = 0;
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (uf.find(u) != uf.find(v)) {
                uf.union(u, v);
                cost += w;
            }
        }
        
        return cost;
    }
    
    class UnionFind {
        int[] parent;
        
        public UnionFind(int n) {
            parent = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
            }
        }
        
        public int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);
            }
            return parent[x];
        }
        
        public void union(int x, int y) {
            parent[find(x)] = find(y);
        }
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 1168 (Optimize Water Distribution in a Village)?

This page provides optimized solutions for LeetCode problem 1168 (Optimize Water Distribution in a Village) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 1168 (Optimize Water Distribution in a Village)?

The time complexity for LeetCode 1168 (Optimize Water Distribution in a Village) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 1168 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 1168 in Java, C++, or Python.

Back to LeetCode Solutions