Node With Highest Edge Score - Video Solutions

Problem Overview: You are given an array edges where index i has a directed edge to edges[i]. The edge score of a node is the sum of indices of nodes pointing to it. Your task is to compute the score for every node and return the node with the highest score (smallest index if there is a tie).

Approach 1: Brute Force Score Calculation (O(n²) time, O(1) space)

The straightforward idea is to compute the score of each node by scanning the entire edges array and summing all indices i where edges[i] == node. This means for every node j, you iterate through all n elements to check incoming edges. While the implementation is simple and uses constant extra space, it performs redundant scans and becomes inefficient for large inputs. This approach mainly helps you reason about how scores are defined before optimizing the solution.

Approach 2: Using an Array to Keep Score (O(n) time, O(n) space)

A more efficient approach accumulates scores in a dedicated array. Create a score array of size n, initialized to zero. Iterate once through the edges array. For each index i, add i to score[edges[i]]. This directly builds the total edge score for every node in a single pass. After filling the score array, scan it once more to find the node with the maximum score, resolving ties by selecting the smallest index. This method runs in linear time and works well because node IDs are already within the range [0, n-1]. Conceptually, the structure behaves like an adjacency accumulation in a graph.

Approach 3: Using a Hash Map for Flexibility (O(n) time, O(n) space)

If node identifiers were sparse or outside a predictable range, a hash map would be more flexible than a fixed array. Iterate through edges and update a map where the key is the destination node and the value stores the running score. Each iteration performs a constant-time hash lookup and addition. After building the map, iterate through the keys to determine the node with the maximum score. This approach uses the same accumulation idea as the array method but relies on a hash table for dynamic storage. It’s slightly heavier in memory and constant factors but easier to adapt when node IDs are not bounded.

Recommended for interviews: The array accumulation approach is the expected solution. It demonstrates that you recognize the fixed node range and can compute scores in one linear pass. Mentioning the brute force method first shows understanding of the scoring definition, while transitioning to the O(n) array solution shows optimization skills. The hash map version is useful to discuss when the problem generalizes beyond a fixed-size node set.