Minimum Cost to Supply Water with Wells and Pipes
Updated
Problem statement
There are n houses, numbered from 1 to n. Every house needs water.
A house can get water in two ways:
- Build a well at the house. Building a well at house
icostswells[i - 1]. - Get water from another house through pipes.
pipes[j] = [house1, house2, cost]means you may lay a pipe betweenhouse1andhouse2forcost. Water can flow through a pipe in both directions, and through any number of pipes in a row.
Choose which wells to build and which pipes to lay so that every house is either a well house or connected by laid pipes to a well house. Return the smallest possible total cost.
There may be several pipe offers between the same two houses, with different costs.
Function
minCostToSupplyWater(n: int, wells: int[], pipes: int[][]) → intExamples
Example 1
n = 4wells = [5,2,8,6]pipes = [[1,2,1],[2,3,3],[3,4,2],[1,4,9]]return = 8Build one well at house 2 for 2. Lay the pipes 1-2 (1), 2-3 (3), and 3-4 (2). Every house is now joined to house 2, and the total is 2 + 1 + 3 + 2 = 8.
Example 2
n = 3wells = [1,1,1]pipes = [[1,2,5],[2,3,5]]return = 3Each well costs 1 and each pipe costs 5, so build a well at every house: 1 + 1 + 1 = 3.
Example 3
n = 2wells = [4,9]pipes = [[1,2,7],[1,2,3]]return = 7There are two pipe offers between houses 1 and 2. Build a well at house 1 (4) and use the cheaper pipe (3): 4 + 3 = 7. Two wells would cost 4 + 9 = 13.
Constraints
2 <= n <= 10^4wells.length == n0 <= wells[i] <= 10^51 <= pipes.length <= 10^4pipes[j].length == 31 <= house1, house2 <= n0 <= cost <= 10^5house1 != house2
More Infosys Online Assessment questions
- Lowest Common Ancestor with a Changing RootOA · Seen Nov 2026
- Minimum Leaf Path Sum over All RootsOA · Seen Nov 2026
- Split Array to Minimize the Largest SumOA · Seen Nov 2026
- Cherry PickupOA · Seen Nov 2026
- Lexicographically Smallest Grid Path with One Letter ChangeOA · Seen Nov 2026
- Minimum Cost to Tile a Strip with Widths 1, 2, and 3OA · Seen Nov 2026
- Minimum Rounds to Complete All TasksOA · Seen Nov 2026
- Count Equal-Distinct Character PartitionsOA · Seen Oct 2026
- Maximum Alternating-Index Packet ValueOA · Seen Oct 2026
- Usable Water with Contaminated PillarsOA · Seen Oct 2026
Similar questions at other companies
- Doctor Appointment Slot AssignmentDRW · OADRW interview questions
- Maximum Edge Removals for Two TravelersMorgan Stanley · ONSITE INTERVIEWMorgan Stanley interview questions
- Water Supply With Wells and PipesNutanix · ONSITE INTERVIEWNutanix interview questions
- Minimum Cost for Roads and HospitalsAmazon · ONSITE INTERVIEW
- Recoverable Elements from Range-Sum MeasurementsEthos Life · OA
- Optimal TransferVisa · OAVisa interview questions
- Divide Tree NodesGoogle · OA · ONSITE INTERVIEWGoogle interview questions
- Biggest Connected ComponentCodeium · OACodeium interview questions
- Disaster RecoveryHeadlands Technologies · OAHeadlands Technologies interview questions
- Minimum Paired Height-Lowering OperationsAdobe · OAAdobe interview questions