Meta / Microsoft Interview Question — LeetCode 1168

In this post, we are going to discuss leetcode 1168 — Optimize Water Distribution in a Village, which is asked in Meta, and Microsoft interviews.

Problem Analysis

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…