1168. Optimize Water Distribution in a Village

How to solve Optimize Water Distribution in a Village (LeetCode 1168): the approach in brief

The problem

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

Pattern

Optimize Water Distribution in a Village is a Graph Traversal Patterns (DFS & BFS) problem, in the Minimum Spanning Tree (Kruskal / Prim / DSU + heap) subpattern. The pattern covers DFS/BFS traversal, topological sort, shortest paths, Union-Find, and MST

Find minimum spanning tree using Kruskal's or Prim's algorithm with Union-Find or heap.

Approach outline

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.

Complexity

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

Asked at

Optimize Water Distribution in a Village has been reported in interviews at Google, Facebook, Yahoo.