Water Connection Problem

The problem, simply

A village has n houses numbered 1 to n and p one-way pipes. Pipe (a, b, d) carries water from house a to house b and has width d. Every house has at most one pipe going out and at most one pipe coming in, so the pipes form separate chains.

Put a tank on every house that has a pipe going out but none coming in. Put a tap on the house where that chain ends. For each tank, report the tank house, the tap house, and the smallest pipe width along the chain, because that is how much water can get through. List them by tank house number.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do not build anything. For each house, read the whole pipe list to see whether a pipe leaves it and whether a pipe enters it. To follow a chain, read the whole list again at every step to find the next pipe.

class Solution {
    // pipes[i] = {from, to, width}; answer rows are {tank, tap, smallest width}
    public List<int[]> solve(int n, int[][] pipes) {
        List<int[]> answer = new ArrayList<>();
        for (int h = 1; h <= n; h++) {
            int[] out = pipeFrom(h, pipes);
            if (out == null || hasPipeInto(h, pipes)) continue;   // not the start of a chain
            int cur = h, smallest = Integer.MAX_VALUE;
            for (int[] p = out; p != null; p = pipeFrom(cur, pipes)) {
                smallest = Math.min(smallest, p[2]);
                cur = p[1];
            }
            answer.add(new int[]{h, cur, smallest});
        }
        return answer;
    }

    private int[] pipeFrom(int h, int[][] pipes) {
        for (int[] p : pipes) if (p[0] == h) return p;
        return null;
    }

    private boolean hasPipeInto(int h, int[][] pipes) {
        for (int[] p : pipes) if (p[1] == h) return true;
        return false;
    }
}

How long it takes: every house and every step along a chain reads all p pipes, so O(n * p). Extra room: nothing besides the answer, O(1).

Way 2: the clever way

Read the pipe list once and write down three small tables, one slot per house: where its pipe goes (to), how wide that pipe is (width), and whether a pipe comes in (hasIn). Now every question is one look-up.

1. For each pipe (a, b, d): to[a] = b, width[a] = d, hasIn[b] = true.
2. For each house h from 1 to n: if hasIn[h] is false and to[h] is not 0, it starts a chain.
3. Follow to[] from h until a house has no pipe out. Keep the smallest width on the way. Record (h, end, smallest).

Because houses go from 1 to n, the answer comes out sorted by tank house for free.

import java.util.*;

class Solution {
    // pipes[i] = {from, to, width}; houses are 1 to n; answer rows are {tank, tap, smallest width}
    public List<int[]> solve(int n, int[][] pipes) {
        int[] to = new int[n + 1];          // 0 means no pipe out
        int[] width = new int[n + 1];
        boolean[] hasIn = new boolean[n + 1];
        for (int[] p : pipes) {
            to[p[0]] = p[1];
            width[p[0]] = p[2];
            hasIn[p[1]] = true;
        }
        List<int[]> answer = new ArrayList<>();
        for (int h = 1; h <= n; h++) {
            if (hasIn[h] || to[h] == 0) continue;     // only chain starts get a tank
            int cur = h, smallest = Integer.MAX_VALUE;
            while (to[cur] != 0) {                    // follow the arrows
                smallest = Math.min(smallest, width[cur]);
                cur = to[cur];
            }
            answer.add(new int[]{h, cur, smallest});
        }
        return answer;
    }
}

How long it takes: building the tables is O(p). The chains never share a house, so all the following together visits each house at most once. Total O(n + p). Extra room: three tables of size n + 1, O(n).

Watch out for

• A loop of pipes has no start, so it produces no tank. Because we only start from houses with no pipe in, the while loop can never run around a loop forever.
• Houses are numbered from 1, so size the tables n + 1.
• The water amount is the smallest width on the chain, not the sum or the last pipe.
• If the input could have two pipes leaving one house, the chains would branch and this is no longer the same problem. Ask about it.

What interviewers ask next

• Why is it O(n + p) and not O(n * chain length)? Each house belongs to at most one chain, and each chain is followed once, from its start.
• Could you use depth first search? Yes. Run it from each start house, carrying the smallest width so far. On chains it does the same walk.
• What if houses can have many pipes out, and you want the biggest amount of water from a tank to a tap? Then the narrowest pipe on a path matters, and you want the path whose narrowest pipe is widest. That is the widest path problem, solved with a Dijkstra-like search using max and min.
• How do you spot a loop? A house with a pipe in and a pipe out that is never reached from any start belongs to a loop.

Remember this

Grown-up words: the houses and pipes are a directed weighted graph, a house with no pipe in has in-degree 0, the end of a chain has out-degree 0, the three tables are adjacency arrays, and the narrowest pipe is the bottleneck of the path.