Node With Highest Edge Score

Problem

You are given a directed graph with n nodes labeled from 0 to n - 1, where each node has exactly one outgoing edge.

The graph is represented by a given 0-indexed integer array edges of length n, where edges[i] indicates that there is a directed edge from node i to node edges[i].

The edge score of a node i is defined as the sum of the labels of all the nodes that have an edge pointing to i.

Return the node with the highest edge score. If multiple nodes have the same edge score, return the node with the smallest index.

Examples

Example 1:

graph TD;
	0 --> 1
	2 --> 0
	3 --> 0
	4 --> 0

	6 --> 7
	5 --> 7
	7 --> 5

1
2
3
4
5
6
7
8


Input: edges = [1,0,0,0,0,7,7,5]
Output: 7
Explanation:
- The nodes 1, 2, 3 and 4 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 + 3 + 4 = 10.
- The node 0 has an edge pointing to node 1. The edge score of node 1 is 0.
- The node 7 has an edge pointing to node 5. The edge score of node 5 is 7.
- The nodes 5 and 6 have an edge pointing to node 7. The edge score of node 7 is 5 + 6 = 11.
Node 7 has the highest edge score so return 7.

Example 2:

graph TD;
	1 --> 0
	0 --> 2
	2 --> 0
	3 --> 2

1
2
3
4
5
6


Input: edges = [2,0,0,2]
Output: 0
Explanation:
- The nodes 1 and 2 have an edge pointing to node 0. The edge score of node 0 is 1 + 2 = 3.
- The nodes 0 and 3 have an edge pointing to node 2. The edge score of node 2 is 0 + 3 = 3.
Nodes 0 and 2 both have an edge score of 3. Since node 0 has a smaller index, we return 0.

Solution

Method 1 - Iterative Solution

Here is the approach:

Traverse the input edges to accumulate scores for each node pointed to by an edge.
Iterate through the scores array to find the node with the highest score.

Note: In Java, use a long type for the scores array to prevent int overflow, which could lead to incorrect results.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


public class Solution {
    public int edgeScore(int[] edges) {
        int n = edges.length, ans = 0;
        long[] scores = new long[n];

        // Calculate the score for each node
        for (int src = 0; src < n; src++) {
            scores[edges[src]] += src;  // Add the index to the score of the destination node
        }

        // Find the node with the highest score
        for (int i = 0; i < n; ++i) {
            if (scores[i] > scores[ans]) {
                ans = i;
            }
        }

        return ans;  // Return the node with the highest edge score
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16


class Solution:
    def edgeScore(self, edges):
        n = len(edges)
        scores = [0] * n

        # Calculate the score for each node
        for src in range(n):
            scores[edges[src]] += src  # Add the index to the score of the destination node

        # Find the node with the highest score
        ans = 0
        for i in range(n):
            if scores[i] > scores[ans]:
                ans = i

        return ans  # Return the node with the highest edge score

Complexity

⏰ Time complexity: O(n), where n is edge length
🧺 Space complexity: O(n)

Problem#

Examples#

Solution#

Method 1 - Iterative Solution#

Code#

Complexity#