Practice/Amazon/Leetcode 1168. Optimize Water Distribution in a Village

Leetcode 1168. Optimize Water Distribution in a Village

CodingMust

Problem

A new residential development has n houses numbered from 1 to n. Each house needs access to water, which can be provided in two ways:

1. Build a private well at the house at a specific cost
2. Connect via pipes to another house that already has water access

You are given:

• n: the number of houses
• wells: an array where wells[i-1] is the cost to build a well at house i
• pipes: an array where each element [house1, house2, cost] represents the cost to lay a bidirectional pipe between house1 and house2

Your task is to determine the minimum total cost to ensure every house has access to water.

Requirements

1. Return the minimum total cost as an integer
2. Every house must have water access either through its own well or through pipes connected to a house with a well
3. Pipes are bidirectional - water can flow in either direction
4. A house connected via pipes to any house with a well will have water access

Constraints

• 1 ≤ n ≤ 10,000
• wells.length == n
• 0 ≤ wells[i] ≤ 100,000
• 1 ≤ pipes.length ≤ 10,000
• pipes[i].length == 3
• 1 ≤ house1, house2 ≤ n
• 0 ≤ cost ≤ 100,000
• house1 ≠ house2

Examples

Example 1:

` Input: n = 3, wells = [1, 2, 2], pipes = [[1, 2, 1], [2, 3, 1]] Output: 3 Explanation: We can supply water to all houses with minimum cost 3:

• Build a well at house 1 for cost 1
• Connect house 1 to house 2 with a pipe for cost 1
• Connect house 2 to house 3 with a pipe for cost 1 Total: 1 + 1 + 1 = 3 `

Example 2:

Input: n = 2, wells = [1, 1], pipes = [[1, 2, 10]] Output: 2 Explanation: Building individual wells at both houses costs 1 + 1 = 2, which is cheaper than building one well and using the expensive pipe (1 + 10 = 11).

Example 3:

Input: n = 5, wells = [5, 4, 3, 2, 1], pipes = [[1, 2, 1], [2, 3, 1], [3, 4, 1], [4, 5, 1]] Output: 5 Explanation: Build a well at house 5 (cheapest at cost 1), then connect all other houses through the pipe network (4 pipes × cost 1 = 4). Total: 5