Water Connection Problem

Medium
1684.

Water Connection Problem

Water Connection Problem is a medium coding problem on depth-first search and graph, asked in Microsoft and Flipkart interviews.

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 <= 20
  • 1 <= p <= n
  • a.length == b.length == d.length == p
  • 1 <= a[i], b[i] <= n, a[i] != b[i]
  • 1 <= d[i] <= 100
  • each house has at most one outgoing and at most one incoming pipe
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} n
 * @param {number} p
 * @param {number[]} a
 * @param {number[]} b
 * @param {number[]} d
 * @return {number[][]}
 */
var solve = function(n, p, a, b, d) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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 <= 20
  • 1 <= p <= n
  • a.length == b.length == d.length == p
  • 1 <= a[i], b[i] <= n, a[i] != b[i]
  • 1 <= d[i] <= 100
  • each house has at most one outgoing and at most one incoming pipe

Hints for Water Connection Problem

  1. Hint 1

    With at most one pipe in and one pipe out per house, the pipes split into simple chains and closed loops.

  2. Hint 2

    A chain starts exactly at a house that has an outgoing pipe and no incoming one — that is the tank.

  3. Hint 3

    Store next[house] and diameter[house], then from each tank follow next until 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

  1. For every pipe i, set next[a[i]] = b[i], diam[a[i]] = d[i] and mark b[i] as having an incoming pipe.
  2. For each house h from 1 to n: if it has an outgoing pipe and no incoming pipe, it is a tank.
  3. From a tank, follow next until reaching a house with no outgoing pipe (the tap), tracking the minimum diam seen.
  4. Append [h, tap, minimum]; the loop over h already 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 res

Java

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