# Node With Highest Edge Score
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/node-with-highest-edge-score)
Canonical: https://scaleengineer.com/dsa/problems/node-with-highest-edge-score
**Data structures:** Hash Table, Graph
**Companies:** [Juspay](https://scaleengineer.com/companies/juspay)
---
## 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.

**Example 1:**

![](https://assets.glich.co/dsa/node-with-highest-edge-score/image0.png) 

**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:**

![](https://assets.glich.co/dsa/node-with-highest-edge-score/image1.png) 

**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`

# Approaches
## Brute Force with Nested Loops
This approach directly translates the problem definition into code. It iterates through each node and, for each node, iterates through all edges again to find all incoming connections and calculate its score. This is straightforward but inefficient for the given constraints.
**Time:** O(n^2), where n is the number of nodes. For each of the n nodes, we iterate through the entire `edges` array of size n to find all incoming edges. This results in a nested loop structure, making it too slow for the problem's constraints. · **Space:** O(1). We only use a few variables to keep track of the maximum score and the corresponding node, requiring constant extra space regardless of the input size.
**Pros:** Simple to understand and implement.; Uses constant extra space, O(1), making it very memory-efficient.
**Cons:** Highly inefficient due to the O(n^2) time complexity.; Will likely result in a 'Time Limit Exceeded' (TLE) error for inputs where n is large (e.g., n = 10^5).
### Explanation
The brute-force method calculates the edge score for each node one by one. To find the score of a specific node `j`, we must scan the entire `edges` array to find all source nodes `i` that point to `j`. 

We can use a nested loop structure. The outer loop iterates through every node `j` from `0` to `n-1`, treating it as the destination node. For each `j`, the inner loop iterates through every node `i` from `0` to `n-1`, treating it as a potential source node. If `edges[i]` is equal to `j`, it means there's an edge from `i` to `j`, so we add `i` to the score of `j`. 

We maintain a variable `maxScore` to keep track of the highest score found so far and `resultNode` for the corresponding node's index. We update these whenever we find a node with a score greater than the current `maxScore`. The tie-breaking rule of returning the smallest index is naturally handled by iterating through the nodes in increasing order and only updating for strictly greater scores.

```java
class Solution {
    public int edgeScore(int[] edges) {
        int n = edges.length;
        long maxScore = -1;
        int resultNode = -1;

        for (int j = 0; j < n; j++) {
            long currentScore = 0;
            for (int i = 0; i < n; i++) {
                if (edges[i] == j) {
                    currentScore += i;
                }
            }

            if (currentScore > maxScore) {
                maxScore = currentScore;
                resultNode = j;
            }
        }
        return resultNode;
    }
}
```
### Algorithm
- Initialize `maxScore` to -1 and `resultNode` to -1.
- Iterate through each node `j` from `0` to `n-1`. This node `j` is the potential destination node whose score we want to calculate.
- For each `j`, initialize `currentScore = 0`.
- Start an inner loop, iterating through each node `i` from `0` to `n-1`. This node `i` is the potential source node.
- Inside the inner loop, check if there is an edge from `i` to `j` (i.e., if `edges[i] == j`).
- If an edge exists, add the label of the source node, `i`, to `currentScore`.
- After the inner loop completes, `currentScore` holds the total edge score for node `j`.
- Compare `currentScore` with `maxScore`. If `currentScore` is strictly greater, update `maxScore = currentScore` and `resultNode = j`.
- After the outer loop finishes, `resultNode` will hold the answer. The tie-breaking rule (smallest index) is handled automatically because we iterate `j` from `0` to `n-1` and only update for a strictly greater score.

## Single Pass with Score Array
A much more efficient approach is to calculate the scores for all nodes in a single pass. We can use an auxiliary array to store the scores. By iterating through the `edges` array just once, we can accumulate the scores for each destination node, avoiding the expensive nested loop.
**Time:** O(n), where n is the number of nodes. We perform two separate, non-nested passes: one to populate the `scores` array and another to find the maximum score. The total time is O(n) + O(n) = O(n). · **Space:** O(n). We use an auxiliary array of size n to store the edge scores for each node. This is the dominant factor in space usage.
**Pros:** Optimal time complexity of O(n), making it very fast and efficient.; Handles the given constraints with ease.; The logic is still straightforward and easy to follow.
**Cons:** Requires O(n) extra space for the scores array, which might be a concern for extremely memory-constrained environments, though it's acceptable for this problem.
### Explanation
The inefficiency of the brute-force approach comes from repeatedly scanning the `edges` array. We can optimize this by changing our perspective. Instead of asking "what nodes point to me?" for each node, we can process each edge and say "I am contributing my label's value to my destination's score."

This leads to a two-pass linear time solution. In the first pass, we create an auxiliary array, `scores`, of size `n` to store the edge score for each node. A `long` array is necessary because the sum of labels can exceed the maximum value of a 32-bit integer. We iterate through the `edges` array from `i = 0` to `n-1`. For each edge from `i` to `edges[i]`, we add `i` to `scores[edges[i]]`.

After this first pass, `scores[j]` will hold the total edge score for each node `j`. In the second pass, we simply iterate through the `scores` array to find the index that has the highest value. We maintain a `maxScore` and a `resultNode` and update them as we find higher scores. The tie-breaking rule is handled correctly by iterating from index 0 and only updating for strictly greater scores.

```java
class Solution {
    public int edgeScore(int[] edges) {
        int n = edges.length;
        // Use long for scores to prevent overflow, as the sum of indices can be large.
        long[] scores = new long[n];

        // First pass: calculate the score for each node.
        for (int i = 0; i < n; i++) {
            int destinationNode = edges[i];
            scores[destinationNode] += i;
        }

        // Second pass: find the node with the highest score.
        long maxScore = -1;
        int resultNode = -1;

        for (int i = 0; i < n; i++) {
            if (scores[i] > maxScore) {
                maxScore = scores[i];
                resultNode = i;
            }
        }
        
        return resultNode;
    }
}
```
### Algorithm
- Get the number of nodes, `n`, from the length of the `edges` array.
- Create a `long` array named `scores` of size `n` and initialize all its elements to `0`. This array will store the edge score for each node.
- Iterate through the `edges` array with an index `i` from `0` to `n-1`.
- For each `i`, the edge is from `i` to `edges[i]`. Add the score contribution `i` to the destination node: `scores[edges[i]] += i`.
- After the loop, the `scores` array contains the final edge score for every node.
- Initialize `maxScore = -1` and `resultNode = -1`.
- Iterate through the `scores` array from index `i = 0` to `n-1`.
- If `scores[i]` is greater than `maxScore`, update `maxScore = scores[i]` and `resultNode = i`.
- Return `resultNode`.

# Solutions
### Java

```java
class Solution {
public
  int edgeScore(int[] edges) {
    int n = edges.length;
    long[] cnt = new long[n];
    for (int i = 0; i < n; ++i) {
      cnt[edges[i]] += i;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (cnt[ans] < cnt[i]) {
        ans = i;
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int edgeScore(vector<int> &edges) {
    int n = edges.size();
    vector<long long> cnt(n);
    for (int i = 0; i < n; ++i) {
      cnt[edges[i]] += i;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      if (cnt[ans] < cnt[i]) {
        ans = i;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def edgeScore(self, edges: List[int]) -> int: cnt = Counter() for i, v in enumerate(edges): cnt[v] += i ans = 0 for i in range(len(edges)): if cnt[ans] < cnt[i]: ans = i return ans

```