Loud and Rich - Practice Coding Problems

Loud and Rich - Problem

There is a group of n people labeled from 0 to n - 1 where each person has a different amount of money and a different level of quietness.

You are given an array richer where richer[i] = [a_i, b_i] indicates that a_i has more money than b_i, and an integer array quiet where quiet[i] is the quietness of the i-th person.

All the given data in richer are logically correct (i.e., the data will not lead you to a situation where x is richer than y and y is richer than x at the same time).

Return an integer array answer where answer[x] = y if y is the least quiet person (that is, the person y with the smallest value of quiet[y]) among all people who definitely have equal to or more money than the person x.

Input & Output

Example 1 — Basic Wealth Hierarchy

$ Input: richer = [[1,0],[2,1],[3,1],[3,7],[4,3],[5,3],[6,3]], quiet = [3,2,5,4,6,1,7,0]

› Output: [5,5,2,5,4,5,6,7]

💡 Note: For person 0: People with ≥ money are {0,1,2,3,4,5,6}, quietest is 5 (quiet=1). For person 1: People with ≥ money are {1,2,3,4,5,6}, quietest is 5 (quiet=1).

Example 2 — Simple Chain

$ Input: richer = [[1,0]], quiet = [1,0]

› Output: [1,1]

💡 Note: Person 1 is richer than person 0. For person 0: can reach {0,1}, quietest is 1. For person 1: can only reach {1}, so answer is 1.

Example 3 — No Relationships

$ Input: richer = [], quiet = [0]

› Output: [0]

💡 Note: Only one person with no wealth relationships, so each person's quietest reachable person is themselves.

Constraints

1 ≤ n ≤ 500
0 ≤ richer.length ≤ n * (n-1) / 2
0 ≤ a_i, b_i < n
a_i != b_i
All pairs (a_i, b_i) are distinct
The observations in richer are all logically consistent

Visualization

Tap to expand

Understanding the Visualization

Input

Wealth relationships and quietness values

Process

Build graph and find quietest reachable for each person

Output

Array where answer[i] is quietest person reachable from person i

Key Takeaway

🎯 Key Insight: Model as directed graph and use DFS with memoization to efficiently find quietest reachable person for each node

Asked in

G Google 12 F Facebook 8 A Amazon 6

The key insight is to model this as a directed graph where edges point from poorer to richer people, then use DFS with memoization to find the quietest reachable person. Best approach is DFS with memoization achieving Time: O(n + m), Space: O(n + m).

Common Approaches

Approach	Time	Space	Notes
✓ DFS with Memoization	O(n + m)	O(n + m)	Use recursive DFS with memoization to avoid recomputing results
Brute Force with Transitive Closure	O(n² + nm)	O(n + m)	Build complete wealth relationship matrix, then find quietest for each person

DFS with Memoization — Algorithm Steps

Step 1: Build adjacency list where each edge points from poorer to richer person
Step 2: For each person, use DFS to explore all reachable richer people
Step 3: Use memoization to cache results and avoid redundant computations

Visualization

Tap to expand

Step-by-Step Walkthrough

DFS Call

Start DFS from person, check memoization

Explore Neighbors

Recursively explore all richer people

Memoize Result

Cache and return quietest person found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 500

int graph[MAX_N][MAX_N];
int graphSize[MAX_N];
int quiet[MAX_N];
int memo[MAX_N];

int dfs(int person) {
    if (memo[person] != -1) {
        return memo[person];
    }
    
    int quietest = person;
    
    for (int i = 0; i < graphSize[person]; i++) {
        int richerPerson = graph[person][i];
        int candidate = dfs(richerPerson);
        if (quiet[candidate] < quiet[quietest]) {
            quietest = candidate;
        }
    }
    
    memo[person] = quietest;
    return quietest;
}

int* solution(int** richer, int richerSize, int* richerColSize, int* quietArray, int quietSize, int* returnSize) {
    int n = quietSize;
    *returnSize = n;
    int* result = (int*)malloc(n * sizeof(int));
    
    // Initialize
    for (int i = 0; i < n; i++) {
        graphSize[i] = 0;
        memo[i] = -1;
        quiet[i] = quietArray[i];
    }
    
    // Build adjacency list: poor -> rich
    for (int i = 0; i < richerSize; i++) {
        int rich = richer[i][0];
        int poor = richer[i][1];
        graph[poor][graphSize[poor]++] = rich;
    }
    
    for (int i = 0; i < n; i++) {
        result[i] = dfs(i);
    }
    
    return result;
}

int main() {
    // Simplified input for demonstration
    int richerSize = 2;
    int** richer = (int**)malloc(richerSize * sizeof(int*));
    richer[0] = (int*)malloc(2 * sizeof(int));
    richer[1] = (int*)malloc(2 * sizeof(int));
    richer[0][0] = 1; richer[0][1] = 0;
    richer[1][0] = 2; richer[1][1] = 1;
    
    int quietArray[] = {3, 2, 5, 4};
    int quietSize = 4;
    int returnSize;
    
    int* result = solution(richer, richerSize, NULL, quietArray, quietSize, &returnSize);
    
    printf("[");
    for (int i = 0; i < returnSize; i++) {
        printf("%d", result[i]);
        if (i < returnSize - 1) printf(",");
    }
    printf("]\n");
    
    free(result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n + m)

Each person and edge is visited at most once due to memoization

✓ Linear Growth

Space Complexity

O(n + m)

Adjacency list storage, memoization array, and recursion stack

⚡ Linearithmic Space

28.4K Views

Medium Frequency

~25 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

DFS with Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler