{x}
blog image

Node With Highest Edge Score

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.

 

Example 1:

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:

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.

 

Constraints:

  • n == edges.length
  • 2 <= n <= 105
  • 0 <= edges[i] < n
  • edges[i] != i

Solution Explanation: Node With Highest Edge Score

This problem involves finding the node in a directed graph with the highest edge score. The edge score of a node is the sum of the indices of all nodes that have an outgoing edge pointing to it. If multiple nodes share the highest score, we return the node with the smallest index.

Approach:

The most efficient approach uses a single pass through the edges array. We maintain an array cnt to store the edge scores for each node. For each node i in edges, we add its index i to the edge score of the node it points to (edges[i]). While doing this, we also track the node (ans) with the currently highest edge score, updating ans whenever we find a node with a higher score or a node with the same score but a smaller index.

Time Complexity Analysis:

The algorithm iterates through the edges array once. Therefore, the time complexity is O(n), where n is the number of nodes (and edges) in the graph.

Space Complexity Analysis:

We use an array cnt of size n to store the edge scores. Therefore, the space complexity is O(n).

Code Implementation (Python):

class Solution:
    def edgeScore(self, edges: List[int]) -> int:
        n = len(edges)
        cnt = [0] * n  # Initialize edge scores for each node to 0
        ans = 0  # Initialize the node with the highest edge score to 0
 
        for i, j in enumerate(edges):
            cnt[j] += i  # Add the current node's index to the edge score of the target node
            if cnt[ans] < cnt[j] or (cnt[ans] == cnt[j] and j < ans):
                ans = j  # Update ans if a better node is found
 
        return ans

Code Implementation (Java):

class Solution {
    public int edgeScore(int[] edges) {
        int n = edges.length;
        long[] cnt = new long[n]; //Using long to avoid potential integer overflow
        int ans = 0;
 
        for (int i = 0; i < n; i++) {
            int j = edges[i];
            cnt[j] += i;
            if (cnt[ans] < cnt[j] || (cnt[ans] == cnt[j] && j < ans)) {
                ans = j;
            }
        }
        return ans;
    }
}

Code Implementation (C++):

class Solution {
public:
    int edgeScore(vector<int>& edges) {
        int n = edges.size();
        vector<long long> cnt(n, 0); // Using long long to avoid potential integer overflow.
        int ans = 0;
 
        for (int i = 0; i < n; ++i) {
            int j = edges[i];
            cnt[j] += i;
            if (cnt[ans] < cnt[j] || (cnt[ans] == cnt[j] && j < ans)) {
                ans = j;
            }
        }
        return ans;
    }
};

The other language implementations (Go, TypeScript, Rust) follow a very similar structure, adapting the syntax appropriately. Note the use of long or long long in Java and C++ respectively. This is to prevent potential integer overflow issues if the edge scores become very large. This doesn't affect the asymptotic complexity.