Water connection problem

Medium

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): []

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
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;
}