Loud and Rich

Medium Graphs Topological Sort Original on LeetCode

Reported atFlipkartPhonePe

Loud and Rich is a medium graphs problem solved with the topological sort pattern. The best approach, optimal (topological order, push answers down), runs in O(n + m) time and O(n + m) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (search from every person) up.

Problem

There are n people numbered 0 to n - 1. Each person has a distinct quietness level quiet[i] (smaller means quieter). You also get a list of facts richer, where richer[i] = [a, b] says person a has strictly more money than person b. The facts never contradict each other, but they may be incomplete.

For every person x, look at all people who are certainly at least as rich as x (that is x itself plus everyone who is richer by some chain of facts) and pick the quietest one. Return an array answer where answer[x] is that person.

Examples

Example 1

Input
richer = [[1, 0], [2, 1], [3, 1]], quiet = [3, 2, 0, 1]
Output
[2, 2, 2, 3]
Why
Persons 1, 2 and 3 all have at least as much money as person 0, and person 2 is the quietest of them (quiet 0). Person 3 has no one known to be richer, so the answer for 3 is 3 itself.

Example 2

Input
richer = [], quiet = [0]
Output
[0]
Why
A single person is always their own answer.

Example 3

Input
richer = [[0, 1], [1, 2]], quiet = [2, 0, 1]
Output
[0, 1, 1]
Why
Person 2 is poorer than 1, who is poorer than 0; among {0, 1, 2} person 1 is quietest.

Constraints

  • 1 <= n == quiet.length <= 500
  • 0 <= quiet[i] < n and all quiet values are distinct.
  • 0 <= richer.length <= n * (n - 1) / 2, richer[i] = [a, b] with a != b, all pairs distinct.
  • The facts are consistent: nobody is (transitively) richer than themselves.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (search from every person)O(n · (n + m))O(n + m)
Optimal (topological order, push answers down)O(n + m)O(n + m)

1Brute force (search from every person)

TimeO(n · (n + m))One full graph search of n nodes and m edges per person.
SpaceO(n + m)Adjacency lists plus a visited array and a stack.

For each person x, walk the graph upward (from a person to everyone known to be richer) and collect every reachable person, keeping the one with the smallest quiet value.

  1. Build up[b] = list of people directly richer than b.
  2. For each x: run a DFS/BFS from x over up, with a fresh visited array.
  3. Among all visited people (x included), pick the one with the smallest quiet value.
class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<List<Integer>> up = new ArrayList<>();
        for (int i = 0; i < n; i++) up.add(new ArrayList<>());
        for (int[] r : richer) up.get(r[1]).add(r[0]);
        int[] ans = new int[n];
        for (int x = 0; x < n; x++) {
            boolean[] seen = new boolean[n];
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(x);
            seen[x] = true;
            int best = x;
            while (!stack.isEmpty()) {
                int cur = stack.pop();
                if (quiet[cur] < quiet[best]) best = cur;
                for (int nxt : up.get(cur)) {
                    if (!seen[nxt]) {
                        seen[nxt] = true;
                        stack.push(nxt);
                    }
                }
            }
            ans[x] = best;
        }
        return ans;
    }
}

2Optimal (topological order, push answers down)

TimeO(n + m)Every person is dequeued once and every fact (edge) is relaxed once.
SpaceO(n + m)Adjacency lists, in-degrees and the queue.

Edges go from richer to poorer, and the graph is a DAG. Start with ans[i] = i. Process people in topological order with Kahn's algorithm: when person a is finished, every richer person has already improved ans[a], so ans[a] is final and can be offered to each poorer neighbour b.

  1. Build down[a] (people directly poorer than a) and indeg[b] (number of direct richer people).
  2. Set ans[i] = i and enqueue everyone with indeg 0.
  3. Pop a; for each b in down[a]: if quiet[ans[a]] < quiet[ans[b]], set ans[b] = ans[a]; decrement indeg[b] and enqueue b when it hits 0.
  4. Return ans.
class Solution {
    public int[] loudAndRich(int[][] richer, int[] quiet) {
        int n = quiet.length;
        List<List<Integer>> down = new ArrayList<>();
        for (int i = 0; i < n; i++) down.add(new ArrayList<>());
        int[] indeg = new int[n];
        for (int[] r : richer) {
            down.get(r[0]).add(r[1]);
            indeg[r[1]]++;
        }
        int[] ans = new int[n];
        Deque<Integer> queue = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            ans[i] = i;
            if (indeg[i] == 0) queue.offer(i);
        }
        while (!queue.isEmpty()) {
            int a = queue.poll();
            for (int b : down.get(a)) {
                if (quiet[ans[a]] < quiet[ans[b]]) ans[b] = ans[a];
                if (--indeg[b] == 0) queue.offer(b);
            }
        }
        return ans;
    }
}

Edge cases to test

  • No facts at all: every answer is the person themselves
  • A person who is quieter than everyone richer than them
  • Long chains, where the answer travels many steps down
  • Several richer people reachable through different paths (diamond shapes)

Hints

Hint 1

Draw an edge from each richer person to each poorer person. Everyone who can reach x along these edges has at least as much money as x.

Hint 2

The answer for x is either x or the answer of one of its direct richer neighbours. Can you compute answers so each neighbour's answer is ready before you need it?

Hint 3

Process people in topological order (richest first) and push each person's best candidate down to the people directly poorer than them.

FAQ

What is the best time complexity for Loud and Rich?

Optimal (topological order, push answers down) runs in O(n + m) time and O(n + m) extra space. Every person is dequeued once and every fact (edge) is relaxed once.

Which pattern does Loud and Rich use?

It is a graphs problem that uses the topological sort pattern. Other problems with the same pattern: Topological sort using BFS, Course Schedule, Course Schedule II.

Is there a brute force solution for Loud and Rich?

Yes. Brute force (search from every person) takes O(n · (n + m)) time and O(n + m) space. For each person x, walk the graph upward (from a person to everyone known to be richer) and collect every reachable person, keeping the one with the smallest quiet value.

Which edge cases should I test for Loud and Rich?

No facts at all: every answer is the person themselves; A person who is quieter than everyone richer than them; Long chains, where the answer travels many steps down; Several richer people reachable through different paths (diamond shapes).