Design a referral leaderboard with chain-based counts

Design and implement a function that generates a referral leaderboard for a platform, given two equal-length arrays rh_users and new_users representing referrals in chronological order (rh_users[i] referred new_users[i]). A user is considered to have referred everyone downstream in their referral chain (e.g., for A -> B -> C -> D, A referred B, C, and D; B referred C and D; C referred D). Requirements:

• Referral rules:
  • A user can be referred at most once.
  • Once a user is on the platform, they cannot be referred by others later.
  • The input pairs appear in the order they were created.
• Leaderboard rules:
  • Include only users with referral count >= 1.
  • Return at most the top 3 users.
  • Sort by descending referral count; break ties by username in ascending lexicographic order.
• Input:
  • rh_users: string[] of referrers.
  • new_users: string[] of referred users, aligned by index with rh_users.
• Output:
  • string[] of up to 3 entries in the form "<user> <count>". Example:
• rh_users = ["A", "B", "C"], new_users = ["B", "C", "D"].
• Output: ["A 3", "B 2", "C 1"]. Discuss your data structures, time and space complexity, and provide runnable code in the language of your choice.

Design a Referral Leaderboard with Chain-Based Counts

You are given two equal-length arrays rh_users and new_users. For each index i, rh_users[i] referred new_users[i], and the pairs appear in the order they were created. The input is guaranteed to be valid: a user is referred at most once, and once a user is already on the platform, they are not referred again later. A user's referral count is the number of all downstream users in their referral tree (all descendants), not just direct referrals. For example, in A -> B -> C -> D, A has count 3, B has count 2, and C has count 1. Return a leaderboard containing only users with count at least 1, sorted by descending referral count and then by username in ascending lexicographic order. Return at most the top 3 entries, each formatted as '<user> <count>'.

Constraints

• 0 <= len(rh_users) == len(new_users) <= 200000
• The referral pairs form a valid forest: each user in new_users appears exactly once and has exactly one referrer
• Usernames are non-empty strings and are compared using standard lexicographic order

Hints

1. Model the referral history as a forest of trees. A user's chain-based referral count is the number of descendants in that user's subtree.
2. Build child lists first, then compute counts bottom-up with a post-order traversal instead of walking up the ancestor chain for every referral.

Approach

The referral graph is a forest: every user in new_users has exactly one referrer, so each node has at most one parent. A user's referral count is its total number of descendants, so we need a subtree-size-minus-one count for every node.

Build the tree. Iterating over the zip(rh_users, new_users) pairs, we populate a children adjacency list, collect every name into all_users, and record each referred name in referred. Any user in all_users but not in referred has in-degree 0 — these are the roots.

Count descendants via iterative post-order DFS. For each root we use an explicit stack of (user, processed) tuples. On the first pop (processed=False) we push the node back as processed=True, then push all its children. When we pop it again (processed=True), every child's count is already final, so we set

The 1 + counts the child itself; counts[child] adds the child's own descendants. Children-before-parent ordering guarantees correctness. The explicit stack matters here: a chain of up to 200k nodes would overflow Python's recursion limit, but the loop handles it safely.

Rank. We keep only count >= 1, sort by (-count, username) so ties break lexicographically ascending, slice the top 3, and format each as "<user> <count>". Empty input yields [], and a single referral yields one entry — both covered by tests.

• Time complexity: O(n + u log u), where n = number of referral pairs and u = number of distinct users. Tree construction and the post-order DFS each touch every node/edge a constant number of times (O(n + u) ≈ O(n)); the final sort over the filtered users dominates at O(u log u).
• Space complexity: O(u). The children map, all_users/referred sets, the counts dict, and the DFS stack are each bounded by the number of distinct users (with n edges stored in children, this is O(n + u) ≈ O(n)).