1168. Optimize Water Distribution in a Village

Optimize Water Distribution in a Village (LeetCode 1168) is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Graph Traversal Patterns (DFS & BFS) pattern, in the Minimum Spanning Tree (Kruskal / Prim / DSU + heap) subpattern.

How to solve Optimize Water Distribution in a Village

Optimize Water Distribution in a Village is a Minimum Spanning Tree problem, part of Graph Traversal Patterns (DFS & BFS). Find minimum spanning tree using Kruskal's or Prim's algorithm with Union-Find or heap.

Work towards the solution in these steps:

1. Think about how you can model the problem as a graph where houses are nodes and pipes are edges with associated costs.
2. Consider that building a well in a house can be treated as connecting that house to a virtual source node with an edge cost equal to the well cost.
3. Explore algorithms for finding a minimum spanning tree (MST) to connect all nodes with the least total cost, such as Kruskal's or Prim's algorithm.

The reference solution runs in O(nlogn) time and O(n) space.

The Optimize Water Distribution in a Village solution and editorial walks through the full approach with reference code.

Problem statement

There are n houses in a village. We want to supply water for all the houses by building wells and laying pipes.

For each house i, we can either build a well inside it directly with cost wells[i - 1] (note the -1 due to 0-indexing), or pipe in water from another well to it. The costs to lay pipes between houses are given by the array pipes, where each pipes[j] = [house1j, house2j, costj] represents the cost to connect house1j and house2j together using a pipe. Connections are bidirectional.

Return the minimum total cost to supply water to all houses.

Example 1: Input: n = 3, wells = [1,2,2], pipes = [[1,2,1],[2,3,1]] Output: 3 Explanation: The image shows the costs of connecting houses using pipes.

The best strategy is to build a well in the first house with cost 1 and connect the other houses to it with cost 2 so the total cost is 3.

Constraints: 1 <= n <= 104 wells.length == n 0 <= wells[i] <= 105 1 <= pipes.length <= 104 pipes[j].length == 3 1 <= house1j, house2j <= n 0 <= costj <= 105 house1j != house2j

Topics and companies

Topics: Union Find, Graph.

Reported in interviews at Google, Facebook, Yahoo.

How to practise Optimize Water Distribution in a Village on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(nlogn) time and O(n) space.

Open Optimize Water Distribution in a Village in the code editor, or read the Optimize Water Distribution in a Village editorial for a worked solution with its approach and complexity analysis.

Where Optimize Water Distribution in a Village sits in the DSA pattern sheet

• Graph Traversal Patterns (DFS & BFS) pattern guide
• Minimum Spanning Tree (Kruskal / Prim / DSU + heap) subpattern
• The full DSA patterns sheet

Problems related to Optimize Water Distribution in a Village

Other problems that use the same Minimum Spanning Tree (Kruskal / Prim / DSU + heap) and Graph Traversal Patterns (DFS & BFS) techniques:

• Connecting Cities With Minimum Cost — Medium, same subpattern
• Min Cost to Connect All Points — Medium, same subpattern
• Accounts Merge — Medium, same pattern
• Alien Dictionary — Hard, same pattern
• All Paths from Source Lead to Destination — Medium, same pattern
• Build a Matrix With Conditions — Hard, same pattern

Optimize Water Distribution in a Village FAQ