Water Connection Problem — Solution in Python, Java & C++
Water Connection Problem solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Water Connection Problem is a medium coding problem on depth-first search and graph, asked in Microsoft and Flipkart interviews.
- Difficulty: Medium
- Topics: Depth-First Search, Graph
- Asked at: Microsoft, Flipkart
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A colony has n houses numbered 1 to n and p water pipes. Pipe i carries water from house a[i] to house b[i] and has diameter d[i]. Every house has at most one outgoing pipe and at most one incoming pipe.
- A house with an outgoing pipe but no incoming pipe gets a tank on its roof.
- A house with an incoming pipe but no outgoing pipe gets a tap.
Water from each tank flows along the chain of pipes until it reaches a tap. The chain can only carry as much as its narrowest pipe allows.
Return one triple [tank, tap, diameter] for every tank — the tank's house, the tap its chain ends at, and the smallest diameter along the chain — sorted by the tank's house number. Houses on a closed loop of pipes have neither a tank nor a tap and are ignored.
Example 1
Input: n = 9, p = 6, a = [7,5,4,2,9,3], b = [4,9,6,8,7,1], d = [98,72,10,22,17,66]
Output: [[2,8,22],[3,1,66],[5,6,10]]
Explanation: Tank 5 feeds 5 → 9 → 7 → 4 → 6 through diameters 72, 17, 98, 10, so the chain carries 10.
Example 2
Input: n = 4, p = 2, a = [1,3], b = [2,4], d = [60,50]
Output: [[1,2,60],[3,4,50]]
Example 3
Input: n = 3, p = 3, a = [1,2,3], b = [2,3,1], d = [5,6,7]
Output: []
Explanation: The pipes form a loop: no house is a tank.
Constraints
1 <= n <= 201 <= p <= na.length == b.length == d.length == p1 <= a[i], b[i] <= n, a[i] != b[i]1 <= d[i] <= 100each house has at most one outgoing and at most one incoming pipe
Hints for Water Connection Problem
Hint 1
With at most one pipe in and one pipe out per house, the pipes split into simple chains and closed loops.
Hint 2
A chain starts exactly at a house that has an outgoing pipe and no incoming one — that is the tank.
Hint 3
Store
next[house]anddiameter[house], then from each tank follownextuntil it runs out, keeping the minimum diameter. Scanning tanks in increasing house order gives the required sort for free.
How to solve Water Connection Problem
Each house has out-degree and in-degree at most one, so the pipe network is a set of disjoint paths and cycles. Each path runs from a tank to a tap, and its capacity is its minimum pipe diameter.
Approach
- For every pipe
i, setnext[a[i]] = b[i],diam[a[i]] = d[i]and markb[i]as having an incoming pipe. - For each house
hfrom1ton: if it has an outgoing pipe and no incoming pipe, it is a tank. - From a tank, follow
nextuntil reaching a house with no outgoing pipe (the tap), tracking the minimumdiamseen. - Append
[h, tap, minimum]; the loop overhalready produces the triples in tank order.
Why it works
A walk from a tank can never revisit a house: a repeat would need some house with two incoming pipes. So it ends at a house with no outgoing pipe, which has an incoming one — a tap. Houses on a cycle all have an incoming pipe, so none is a tank and the cycle is never entered.
Complexity
- Time —
O(n + p) - Space —
O(n)
Pitfalls
- Only start from houses with no incoming pipe; starting from every house with an outgoing pipe would report partial chains and loop forever on cycles.
- The answer is the minimum diameter on the chain, not the first or last pipe's.
- Houses are numbered from 1 — size arrays as
n + 1.
Reference solution
Python
from typing import List
def solve(n: int, p: int, a: List[int], b: List[int], d: List[int]) -> List[List[int]]:
nxt = [0] * (n + 1)
diam = [0] * (n + 1)
has_in = [False] * (n + 1)
for i in range(p):
nxt[a[i]] = b[i]
diam[a[i]] = d[i]
has_in[b[i]] = True
res = []
for h in range(1, n + 1):
if nxt[h] == 0 or has_in[h]:
continue
cur, best = h, 101
while nxt[cur] != 0:
best = min(best, diam[cur])
cur = nxt[cur]
res.append([h, cur, best])
return resJava
public static int[][] solve(int n, int p, int[] a, int[] b, int[] d) {
int[] nxt = new int[n + 1], diam = new int[n + 1];
boolean[] hasIn = new boolean[n + 1];
for (int i = 0; i < p; i++) { nxt[a[i]] = b[i]; diam[a[i]] = d[i]; hasIn[b[i]] = true; }
List<int[]> res = new ArrayList<>();
for (int h = 1; h <= n; h++) {
if (nxt[h] == 0 || hasIn[h]) continue;
int cur = h, best = 101;
while (nxt[cur] != 0) { best = Math.min(best, diam[cur]); cur = nxt[cur]; }
res.add(new int[]{h, cur, best});
}
return res.toArray(new int[0][]);
}C++
vector<vector<int>> solve(int n, int p, vector<int>& a, vector<int>& b, vector<int>& d) {
vector<int> nxt(n + 1, 0), diam(n + 1, 0);
vector<bool> hasIn(n + 1, false);
for (int i = 0; i < p; i++) { nxt[a[i]] = b[i]; diam[a[i]] = d[i]; hasIn[b[i]] = true; }
vector<vector<int>> res;
for (int h = 1; h <= n; h++) {
if (nxt[h] == 0 || hasIn[h]) continue;
int cur = h, best = 101;
while (nxt[cur] != 0) { best = min(best, diam[cur]); cur = nxt[cur]; }
res.push_back({h, cur, best});
}
return res;
}JavaScript
var solve = function(n, p, a, b, d) {
var nxt = [], diam = [], hasIn = [];
for (var i = 0; i <= n; i++) { nxt.push(0); diam.push(0); hasIn.push(false); }
for (var k = 0; k < p; k++) { nxt[a[k]] = b[k]; diam[a[k]] = d[k]; hasIn[b[k]] = true; }
var res = [];
for (var h = 1; h <= n; h++) {
if (nxt[h] === 0 || hasIn[h]) continue;
var cur = h, best = 101;
while (nxt[cur] !== 0) { best = Math.min(best, diam[cur]); cur = nxt[cur]; }
res.push([h, cur, best]);
}
return res;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 201 depth-first search problems · the whole catalogue
Learn the technique: Depth-First Search (DFS) · Graph Data Structure