Problem Description

You have a directed graph with n nodes, where each node is labeled from 0 to n - 1. Each node has exactly one outgoing edge (points to exactly one other node).

The graph is represented by an array edges of length n, where edges[i] tells you that there is a directed edge from node i to node edges[i].

The edge score of a node is calculated by adding up all the labels of nodes that point to it. For example, if nodes 2, 3, and 5 all point to node 7, then the edge score of node 7 would be 2 + 3 + 5 = 10.

Your task is to find the node with the highest edge score. If there's a tie (multiple nodes have the same highest score), return the node with the smallest index.

Example walkthrough:

• If edges = [1, 0, 0, 0, 2], then:

  • Node 0 points to node 1
  • Node 1 points to node 0
  • Node 2 points to node 0
  • Node 3 points to node 0
  • Node 4 points to node 2

• Edge scores would be:

  • Node 0: receives edges from nodes 1, 2, 3 → score = 1 + 2 + 3 = 6
  • Node 1: receives edge from node 0 → score = 0
  • Node 2: receives edge from node 4 → score = 4
  • Nodes 3 and 4: no incoming edges → score = 0

• The answer would be node 0 with the highest score of 6.

Intuition

Since we need to calculate the edge score for each node (the sum of labels of all nodes pointing to it), we can think of this as a counting problem.

The key insight is that we don't need to build the entire graph structure or do any complex traversal. We simply need to track how much "score" each node accumulates from incoming edges.

As we iterate through the edges array, for each node i with its outgoing edge to node edges[i], we know that node i contributes its label value (which is i itself) to the edge score of node edges[i]. So we can maintain a counter array where cnt[j] keeps track of the total edge score for node j.

The clever part is that we can update our answer on the fly as we process each edge. Whenever we update a node's edge score, we immediately check if this node should become our new answer. This way, we only need a single pass through the data.

For handling ties (when multiple nodes have the same score), we need to return the smallest index. So when comparing scores, if we find a node with a higher score, we update our answer. If we find a node with the same score as our current answer, we only update if this new node has a smaller index.

This approach is efficient because:

1. We process each edge exactly once
2. We don't need to store the graph structure
3. We find the answer in a single traversal without needing a separate step to find the maximum

Learn more about Graph patterns.

Solution Approach

We implement the solution using a single traversal approach with an auxiliary array to track edge scores.

Data Structure:

• Create an array cnt of size n where cnt[j] stores the edge score of node j. Initialize all values to 0.
• Maintain a variable ans to track the node with the highest edge score, initially set to 0.

Algorithm Steps:

1. Traverse the edges array: Use enumerate to iterate through edges, getting both index i (the source node) and value j (the destination node).

2. Update edge scores: For each edge from node i to node j:

   • Add i to cnt[j]: cnt[j] += i
   • This accumulates the labels of all nodes pointing to j

3. Update the answer: After updating cnt[j], check if node j should become the new answer:

   • If cnt[ans] < cnt[j]: Node j has a higher score, so update ans = j
   • If cnt[ans] == cnt[j] and j < ans: Node j has the same score but smaller index, so update ans = j

4. Return the result: After processing all edges, return ans

Example walkthrough with edges = [1, 0, 0, 0, 2]:

• Initially: cnt = [0, 0, 0, 0, 0], ans = 0
• i=0, j=1: cnt[1] += 0 → cnt = [0, 0, 0, 0, 0], ans = 0
• i=1, j=0: cnt[0] += 1 → cnt = [1, 0, 0, 0, 0], ans = 0
• i=2, j=0: cnt[0] += 2 → cnt = [3, 0, 0, 0, 0], ans = 0
• i=3, j=0: cnt[0] += 3 → cnt = [6, 0, 0, 0, 0], ans = 0
• i=4, j=2: cnt[2] += 4 → cnt = [6, 0, 4, 0, 0], ans = 0
• Return 0 (highest score is 6)

The time complexity is O(n) as we traverse the edges array once, and space complexity is O(n) for the cnt array.

Example Walkthrough

Let's walk through a small example with edges = [2, 0, 1, 2].

This means:

• Node 0 → Node 2
• Node 1 → Node 0
• Node 2 → Node 1
• Node 3 → Node 2

Step-by-step execution:

Initialize: cnt = [0, 0, 0, 0], ans = 0

Processing edge from node 0 to node 2:

• i = 0, j = 2
• cnt[2] += 0 → cnt = [0, 0, 0, 0]
• Check if we should update ans:
  • cnt[0] = 0 vs cnt[2] = 0 (equal)
  • Since scores are equal but ans = 0 < 2, keep ans = 0

Processing edge from node 1 to node 0:

• i = 1, j = 0
• cnt[0] += 1 → cnt = [1, 0, 0, 0]
• Check if we should update ans:
  • cnt[0] = 1 > cnt[0] = 1 (current ans is already 0)
  • Keep ans = 0

Processing edge from node 2 to node 1:

• i = 2, j = 1
• cnt[1] += 2 → cnt = [1, 2, 0, 0]
• Check if we should update ans:
  • cnt[0] = 1 < cnt[1] = 2 (node 1 has higher score)
  • Update ans = 1

Processing edge from node 3 to node 2:

• i = 3, j = 2
• cnt[2] += 3 → cnt = [1, 2, 3, 0]
• Check if we should update ans:
  • cnt[1] = 2 < cnt[2] = 3 (node 2 has higher score)
  • Update ans = 2

Final result: Return 2 (node 2 has the highest edge score of 3)

The edge scores are:

• Node 0: score = 1 (from node 1)
• Node 1: score = 2 (from node 2)
• Node 2: score = 3 (from nodes 0 and 3: 0 + 3 = 3)
• Node 3: score = 0 (no incoming edges)

Solution Implementation

Time and Space Complexity

The time complexity is O(n), where n is the length of the array edges. The algorithm iterates through the edges array exactly once using enumerate(), performing constant-time operations for each element: accessing and updating the cnt array, comparing values, and potentially updating the ans variable.

The space complexity is O(n), where n is the length of the array edges. This is due to the creation of the cnt array with size equal to len(edges), which stores the accumulated scores for each node. The remaining variables (ans, i, j) use constant space.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Tie-Breaking Logic

A common mistake is implementing the tie-breaking condition incorrectly when multiple nodes have the same highest edge score.

Incorrect Implementation:

# Wrong: This updates even when target_node has a larger index
if edge_scores[max_score_node] <= edge_scores[target_node]:
    max_score_node = target_node

Why it's wrong: Using <= without checking the index means that when scores are equal, we always update to the latest node we encounter, not necessarily the one with the smallest index.

Correct Implementation:

if (edge_scores[max_score_node] < edge_scores[target_node] or 
    (edge_scores[max_score_node] == edge_scores[target_node] and 
     target_node < max_score_node)):
    max_score_node = target_node

2. Integer Overflow in Other Languages

While Python handles large integers automatically, in languages like Java or C++, the sum of node indices could overflow for large graphs.

Problem Example: For a graph with n=100,000 nodes where many nodes point to a single node, the edge score could exceed the range of a 32-bit integer.

Solution: Use appropriate data types:

• Java: Use long[] instead of int[] for edge scores
• C++: Use long long instead of int

// Java example
long[] edgeScores = new long[edges.length];  // Use long to prevent overflow

3. Forgetting to Initialize the Answer Variable

Some implementations might forget to properly initialize the answer variable or start with an invalid node index.

Incorrect:

max_score_node = -1  # Wrong: -1 is not a valid node
# or forgetting to initialize at all

Correct:

max_score_node = 0  # Start with node 0 as the initial answer

This ensures that even if all nodes have an edge score of 0, we still return a valid node (node 0).