851. Loud and Rich
Approach
Build a richer-than graph; DFS with memoization propagates the quietest person reachable from each node.
Key Techniques
Array problems involve manipulating elements stored in a contiguous block of memory. Key techniques include two-pointer traversal, prefix sums, sliding windows, and in-place partitioning. In C#, arrays are zero-indexed and fixed in size — use List<T> when you need dynamic resizing.
DFS explores as far as possible before backtracking. Use it for path finding, cycle detection, connected components, and tree traversal. Implement recursively (implicit call stack) or iteratively with an explicit Stack<T>. Mark visited nodes to avoid infinite loops in graphs.
BFS explores nodes level by level, guaranteeing the shortest path in unweighted graphs. Use a Queue<T> and a visited set. Classic applications: shortest path, level-order tree traversal, multi-source distance (e.g., "01 matrix"), and word ladder transformations.
// Approach: Build a richer-than graph; DFS with memoization propagates the quietest person reachable from each node.
// Time: O(V+E) Space: O(V)
public class Solution
{
public int[] LoudAndRich(int[][] richer, int[] quiet)
{
int n = quiet.Length;
int[] ans = new int[n];
Array.Fill(ans, -1);
var graph = new List<int>[n];
for (int i = 0; i < n; i++)
graph[i] = new List<int>();
foreach (int[] r in richer)
{
int u = r[1];
int v = r[0];
graph[u].Add(v);
}
for (int i = 0; i < n; i++)
DFS(graph, i, quiet, ans);
return ans;
}
private int DFS(List<int>[] graph, int u, int[] quiet, int[] ans)
{
if (ans[u] != -1)
return ans[u];
ans[u] = u;
foreach (int v in graph[u])
{
int res = DFS(graph, v, quiet, ans);
if (quiet[res] < quiet[ans[u]])
ans[u] = res;
}
return ans[u];
}
}