Node With Highest Edge Score

medium graph hash map counting

Problem

You are given a directed graph with n nodes labeled 0 to n−1, where each node i has exactly one outgoing edge to node edges[i]. The edge score of a node is the sum of the labels of all nodes pointing to it. Return the node with the highest edge score; on a tie, return the smallest such index.

Inputedges = [1,0,0,0,0,7,7,5]

Output7

Nodes 5 and 6 point to node 7, so node 7 scores 5 + 6 = 11, the highest total.

Inputedges = [2,0,0,2]

Output0

Nodes 0 and 2 both score 3; node 0 wins the tie with the smaller index.

edges (comma-separated, each 0..n−1, edges[i] ≠ i)

def edge_score(edges):
    n = len(edges)
    score = [0] * n
    for i in range(n):
        score[edges[i]] += i
    best = 0
    for i in range(1, n):
        if score[i] > score[best]:
            best = i
    return best

function edgeScore(edges) {
  const n = edges.length;
  const score = new Array(n).fill(0);
  for (let i = 0; i < n; i++) {
    score[edges[i]] += i;
  }
  let best = 0;
  for (let i = 1; i < n; i++) {
    if (score[i] > score[best]) best = i;
  }
  return best;
}

int edgeScore(int[] edges) {
    int n = edges.length;
    long[] score = new long[n];
    for (int i = 0; i < n; i++) {
        score[edges[i]] += i;
    }
    int best = 0;
    for (int i = 1; i < n; i++) {
        if (score[i] > score[best]) best = i;
    }
    return best;
}

int edgeScore(vector<int>& edges) {
    int n = edges.size();
    vector<long long> score(n, 0);
    for (int i = 0; i < n; i++) {
        score[edges[i]] += i;
    }
    int best = 0;
    for (int i = 1; i < n; i++) {
        if (score[i] > score[best]) best = i;
    }
    return best;
}

Explanation

Each node has exactly one outgoing edge, so the graph is a functional graph. The edge score of a node is the sum of the labels of every node that points to it. We never need the score formula per target up front — we just accumulate it.

We keep an array score of length n, all zeros. We then walk every node i once. The edge from i lands on edges[i], so we add the contributor's label i to score[edges[i]]. After one pass, score[v] holds the full edge score of node v.

Because every node contributes exactly once and a node's own label is the value added, this single pass is enough — no need to build adjacency lists or count in-degrees separately.

Finally we scan score for the maximum. We start with best = 0 and only switch to a later index when its score is strictly greater. Using a strict comparison naturally keeps the smallest index on ties, satisfying the tie-break rule.

Scores can be large (up to about n²/2), so Java and C++ use 64-bit accumulators to avoid overflow when n is near its upper bound.

Time: O(n) Space: O(n)