Water Supply With Wells and Pipes
Updated
Problem statement
A town has n houses, labeled from 1 to n, and every house needs water. There are two ways to bring it in:
- Build a well at house
i. This costswellCost[i - 1]. - Lay a pipe from the list
pipes. Eachpipes[j] = [a, b, c]is a pipe between houseaand housebthat costsc. Water can flow through a pipe in both directions.
A house has water if it has its own well, or if built pipes join it, directly or through other houses, to a house with a well. You may build any number of wells and lay any of the pipes.
Return the smallest total cost that gives water to every house.
Function
minCostToSupplyWater(n: int, wellCost: int[], pipes: int[][]) → intExamples
Example 1
n = 4wellCost = [5,3,6,8]pipes = [[1,2,2],[2,3,4],[3,4,1],[1,4,7]]return = 10Build one well at house 2 for 3, then lay the pipes 1-2 for 2, 2-3 for 4 and 3-4 for 1. Every house is now joined to house 2, so the total is 3 + 2 + 4 + 1 = 10.
Swapping any part for something else costs more. For example, a second well at house 3 (cost 6) instead of the pipe 2-3 (cost 4) gives 12.
Example 2
n = 3wellCost = [2,9,2]pipes = [[1,2,3],[2,3,3],[1,3,10]]return = 7Wells at houses 1 and 3 cost 2 each. House 2 then takes the pipe 1-2 for 3, so the total is 2 + 2 + 3 = 7. The pipe 2-3 would work just as well and gives the same total.
One well is not enough here: a single well at house 1 needs the pipes 1-2 and 2-3, which costs 2 + 3 + 3 = 8.
Example 3
n = 5wellCost = [4,4,4,1,10]pipes = [[1,2,1],[2,3,1],[4,5,2]]return = 9No pipe joins houses 1, 2 and 3 to houses 4 and 5, so each group needs its own well.
Houses 1, 2 and 3: one well for 4 plus the pipes 1-2 and 2-3 for 1 each, which is 6. Houses 4 and 5: a well at house 4 for 1 plus the pipe 4-5 for 2, which is 3. The total is 6 + 3 = 9.
Constraints
1 <= n <= 10^4wellCost.length == n1 <= wellCost[i] <= 10^50 <= pipes.length <= 10^4pipes[j].length == 31 <= pipes[j][0], pipes[j][1] <= npipes[j][0] != pipes[j][1]1 <= pipes[j][2] <= 10^5- The same two houses can be joined by more than one pipe, and the pipes do not have to join all the houses.
More Nutanix Onsite Interview questions
- Design Hit CounterONSITE INTERVIEW · Seen Oct 2026
- Peak Process MemoryONSITE INTERVIEW · Seen Aug 2026
- Minimum Operations to Transform ArrayONSITE INTERVIEW · Seen Jun 2026
- Count Connected Components in an Undirected GraphONSITE INTERVIEW · Seen Aug 2025
- LRU CacheONSITE INTERVIEW · Seen Aug 2025
- Running Median of a Multilevel Linked List in Level OrderONSITE INTERVIEW · Seen Aug 2025
- Custom Array IteratorONSITE INTERVIEW · Seen Dec 2024
- Collapse Runs of Repeated CharactersONSITE INTERVIEW · Seen Nov 2022
- Anagram Words in a SentenceONSITE INTERVIEW · Seen Apr 2022
- Sudoku SolverONSITE INTERVIEW · Seen Feb 2022
Similar questions at other companies
- Maximum Edge Removals for Two TravelersMorgan Stanley · ONSITE INTERVIEWMorgan Stanley interview questions
- Minimum Cost for Roads and HospitalsAmazon · ONSITE INTERVIEW
- Top-K Affinity Nodes in a Connected ComponentGoogle · ONSITE INTERVIEWGoogle interview questions
- Minimum Cost to Supply Water with Wells and PipesInfosys · OAInfosys interview questions
- Maximum Sum of a K-StarMicrosoft · OAMicrosoft interview questions
- Maximum K-Star SumC3.ai · OAC3.ai interview questions
- Doctor Appointment Slot AssignmentDRW · OADRW interview questions
- Scheduled Payments with Account AliasesCoinbase · ONSITE INTERVIEWCoinbase interview questions
- Minimum Refueling StopsUber · ONSITE INTERVIEWUber interview questions
- Find All People With SecretIDFC Bank · ONSITE INTERVIEWIDFC Bank interview questions