GreedyProblem 4 of 35
Water Connection Problem
Problem Statement
There are n houses in a village. We want to supply water to all houses by building tanks and laying pipes. Each pipe can carry water from one house to another with a certain diameter. Water flows from higher numbered house to lower numbered house.
Given p pipes connecting houses, find the minimum number of tanks needed and for each tank, output the house where the tank is installed, the house where the water ends, and the minimum diameter in the path.
Constraints:
- 1 ≤ n ≤ 10^5
- 1 ≤ p ≤ 10^5
- 1 ≤ diameter ≤ 10^9
Example:
- Input:
n = 9,pipes = [(7,4,98), (5,9,72), (4,6,10), (2,8,22), (9,7,17), (3,1,66)] - Output:
3tanks needed- Tank at 2, ends at 8, min diameter 22
- Tank at 3, ends at 1, min diameter 66
- Tank at 5, ends at 6, min diameter 10
Approach 1: Brute Force (Follow Each Path)
Intuition
For each house, check if it's a source (has outgoing pipe but no incoming pipe). Then trace the path from source to destination, tracking minimum diameter.
Algorithm
- For each house, determine if it has incoming/outgoing pipes
- Houses with only outgoing pipes are sources (need tanks)
- For each source, follow the path to find the endpoint
- Track minimum diameter along the path
java
import java.util.*;
public class Solution {
public List<int[]> findTanks(int n, int[][] pipes) {
Map<Integer, int[]> graph = new HashMap<>(); // from -> [to, diameter]
Set<Integer> hasIncoming = new HashSet<>();
Set<Integer> hasOutgoing = new HashSet<>();
// Build graph
for (int[] pipe : pipes) {
int from = pipe[0], to = pipe[1], dia = pipe[2];
graph.put(from, new int[]{to, dia});
hasOutgoing.add(from);
hasIncoming.add(to);
}
List<int[]> result = new ArrayList<>();
// Find sources
for (int house = 1; house <= n; house++) {
if (hasOutgoing.contains(house) && !hasIncoming.contains(house)) {
int source = house;
int current = house;
int minDia = Integer.MAX_VALUE;
while (graph.containsKey(current)) {
minDia = Math.min(minDia, graph.get(current)[1]);
current = graph.get(current)[0];
}
result.add(new int[]{source, current, minDia});
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(n^2) in worst case - checking each house and potentially traversing long paths
- Space Complexity: O(n) - For storing graph and sets
Approach 2: Optimal (Graph Traversal with Indegree/Outdegree)
Intuition
Use in-degree and out-degree arrays to efficiently identify sources. Then use DFS to trace paths efficiently.
Algorithm
- Build adjacency list with in-degree and out-degree counts
- Sources are nodes with out-degree > 0 and in-degree = 0
- DFS from each source to find endpoint and minimum diameter
- Return all (source, end, min_diameter) tuples
java
import java.util.*;
public class WaterConnection {
private int[] to;
private int[] diameter;
private int[] dfs(int node) {
// Returns [endNode, minDiameter]
if (to[node] == 0) {
return new int[]{node, Integer.MAX_VALUE};
}
int[] result = dfs(to[node]);
result[1] = Math.min(result[1], diameter[node]);
return result;
}
public List<int[]> solve(int n, int[][] pipes) {
to = new int[n + 1];
diameter = new int[n + 1];
int[] indegree = new int[n + 1];
int[] outdegree = new int[n + 1];
// Build graph
for (int[] pipe : pipes) {
int a = pipe[0], b = pipe[1], d = pipe[2];
to[a] = b;
diameter[a] = d;
outdegree[a]++;
indegree[b]++;
}
List<int[]> result = new ArrayList<>();
// Find all sources
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0 && outdegree[i] > 0) {
int[] res = dfs(i);
result.add(new int[]{i, res[0], res[1]});
}
}
// Sort by source
result.sort((a, b) -> a[0] - b[0]);
return result;
}
public static void main(String[] args) {
WaterConnection wc = new WaterConnection();
int[][] pipes = {
{7, 4, 98}, {5, 9, 72}, {4, 6, 10},
{2, 8, 22}, {9, 7, 17}, {3, 1, 66}
};
List<int[]> result = wc.solve(9, pipes);
System.out.println(result.size());
for (int[] r : result) {
System.out.println(r[0] + " " + r[1] + " " + r[2]);
}
}
}Dry Run Example
n = 9
pipes = [(7,4,98), (5,9,72), (4,6,10), (2,8,22), (9,7,17), (3,1,66)]
Building graph:
7 -> 4 (dia=98)
5 -> 9 (dia=72)
4 -> 6 (dia=10)
2 -> 8 (dia=22)
9 -> 7 (dia=17)
3 -> 1 (dia=66)
Chains formed:
5 -> 9 -> 7 -> 4 -> 6 (min diameter = min(72,17,98,10) = 10)
2 -> 8 (min diameter = 22)
3 -> 1 (min diameter = 66)
Indegree and Outdegree:
House: 1 2 3 4 5 6 7 8 9
In: 1 0 0 1 0 1 1 1 1
Out: 0 1 1 1 1 0 1 0 1
Sources (in=0, out>0): 2, 3, 5
DFS from source 2: 2 -> 8, minDia = 22
DFS from source 3: 3 -> 1, minDia = 66
DFS from source 5: 5 -> 9 -> 7 -> 4 -> 6, minDia = min(72,17,98,10) = 10
Result:
Tank at 2, ends at 8, min diameter = 22
Tank at 3, ends at 1, min diameter = 66
Tank at 5, ends at 6, min diameter = 10
Complexity Analysis
- Time Complexity: O(n + p)
- Building graph: O(p)
- Finding sources: O(n)
- DFS for all paths: O(p) total (each edge visited once)
- Space Complexity: O(n) - For arrays and recursion stack
Key Takeaways
- Graph Modeling: Model houses as nodes, pipes as directed edges
- Source Identification: Source = indegree 0, outdegree > 0
- Path Bottleneck: Minimum diameter in path determines flow capacity
- Connected Components: Each disjoint path needs one tank
- DFS Traversal: Follow edges to find path end and minimum diameter
- Linear Chains: Each path is a simple chain (no branching)
- Practical Application: Water distribution network optimization