Water connection problem
Problem
n houses are joined by one-way pipes (at most one pipe in and one out per house, each with a diameter). Put a tank at every house with an outgoing pipe but no incoming one, and a tap at the house where that chain ends. For each tank–tap pair, report the smallest diameter along the chain.
Example 1
Input: n = 9, pipes (from, to, d) = [(7,4,98), (5,9,72), (4,6,10), (2,8,22), (9,7,17), (3,1,66)] Output: (2,8,22), (3,1,66), (5,6,10)
Also asked as: Water Connection Problem · Water Connection Problem
Test cases
Case 1
Input: 9, [[7,4,98],[5,9,72],[4,6,10],[2,8,22],[9,7,17],[3,1,66]] Expected (any order): [[2,8,22],[3,1,66],[5,6,10]]
Case 2
Input: 4, [[1,2,10],[2,3,4],[3,4,7]] Expected (any order): [[1,4,4]]
Case 3
Input: 2, [[1,2,5]] Expected (any order): [[1,2,5]]
Case 4
Input: 3, [] Expected (any order): []
View solutionHide solution1 approach
1. Follow each pipe chain from a house with no incoming pipe
Time O(n + p)Space O(n)
Build in/out maps. Every house with an outgoing but no incoming pipe is a tank source; walk the chain to its end (a house with no outgoing pipe), recording the minimum pipe diameter along the way.
function waterConnection(n, pipes) { // pipes: [from, to, diameter] const out = new Map(), incoming = new Set(); for (const [a, b, d] of pipes) { out.set(a, [b, d]); incoming.add(b); } const res = []; for (const [a] of out) { if (incoming.has(a)) continue; let cur = a, minD = Infinity; while (out.has(cur)) { const [nxt, d] = out.get(cur); minD = Math.min(minD, d); cur = nxt; } res.push([a, cur, minD]); // [tank house, tap house, max deliverable diameter] } return res;}