Node With Highest Edge Score

Node With Highest Edge Score

What is this problem about?

The Node With Highest Edge Score problem gives you an array edges where edges[i] is the destination of the directed edge from node i. The "edge score" of a node is the sum of all source node indices pointing to it. Find the node with the highest edge score, with ties broken by returning the smallest node index. This Node With Highest Edge Score coding problem tests hash table aggregation with tiebreaking.

Why is this asked in interviews?

Juspay asks this to test hash map aggregation on directed graphs where each node has exactly one outgoing edge. It validates clean graph traversal combined with running maximum tracking. The hash table and graph interview pattern is the core.

Algorithmic pattern used

Hash map aggregation. Initialize a score array score[n] with zeros. For each node i, add i to score[edges[i]]. After processing all nodes, find the index with the maximum score. On tie, return the smaller index (traverse from index 0 upward, updating best only when strictly greater).

Example explanation

edges = [1, 0, 0, 0, 0, 7, 7, 5]. n=8.

• Node 0 points to 1: score[1] += 0.
• Node 1 points to 0: score[0] += 1.
• Nodes 2,3,4 point to 0: score[0] += 2+3+4 = 9. score[0] = 10.
• Node 5 points to 7: score[7] += 5.
• Nodes 6,7 → score[7] += 6+7 = 13. Wait: node 6 → 7, node 7 → 5.
• Recalculate: score[7] += 6, score[5] += 7. score[1]=0, score[0]=10, score[7]=5+6=11... Max score = 11 at node 7. Return 7.

Common mistakes candidates make

• Adding the edge destination index instead of the source node index to the score.
• Not handling tiebreaking correctly (should return the smallest index with max score).
• Using a dictionary when an array indexed 0..n-1 is more efficient.
• Initializing the max tracker with -1 but not handling the strictly-greater condition for tiebreaking.

Interview preparation tip

Graph aggregation problems where each node has exactly one outgoing edge (functional graph) are common in coding interviews. For each node i, its contribution to its destination is i itself. The score[dest] += source_index pattern is simple once stated. Always verify the tiebreaking condition before coding — "smallest index" means iterate from 0 and update only when strictly greater, not ≥.