Leetcode 2374: Node With Highest Edge Score

Input: The input consists of an integer array `edges` of size n where each element in the array represents an outgoing edge from node i.

Example: edges = [1, 0, 0, 0, 0, 7, 7, 5]

Constraints:

• 2 <= n <= 10^5

• 0 <= edges[i] < n

• edges[i] != i

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

Example: Output: 7

Constraints:

Goal: The goal is to compute the edge score for each node and determine the node with the highest edge score.

Steps:

• 1. Initialize a map to store the sum of edge scores for each node.

• 2. Iterate through the `edges` array and update the edge scores for the target nodes.

• 3. Track the node with the highest edge score, resolving ties by selecting the smallest index.

Goal: The number of nodes in the graph will always be between 2 and 10^5, and each node has an outgoing edge to a distinct target.

Steps:

• The graph will always have at least 2 nodes.

• Each node points to a valid target node, and no node points to itself.

Assumptions:

• The graph is a directed graph where each node has exactly one outgoing edge.

• Input: Input: edges = [1, 0, 0, 0, 0, 7, 7, 5]

• Explanation: For this input, node 0 has the highest edge score, as the sum of labels of nodes pointing to it is 10 (nodes 1, 2, 3, 4). Node 7 has an edge score of 11 (nodes 5 and 6), which is the highest, so the output is 7.

• Input: Input: edges = [2, 0, 0, 2]

• Explanation: In this case, both nodes 0 and 2 have an edge score of 3. Since node 0 has the smallest index, the output is 0.

Approach: This problem can be solved by keeping track of the sum of node labels for each target node. The solution involves iterating over the array and updating the edge scores for each target node.

Observations:

• We need to track the sum of node labels for each target node to calculate the edge scores.

• We should efficiently track the node with the highest edge score while handling ties.

• A hashmap is an efficient choice to store edge scores and resolve ties based on the node index.

Steps:

• 1. Create a map `mp` to store the edge score for each node.

• 2. Traverse the `edges` array, adding the current node index to the edge score of the target node.

• 3. Track the node with the highest edge score, updating the result when a higher score is found or resolving ties by checking the node index.

Empty Inputs:

• There will always be at least two nodes in the input.

Large Inputs:

• The solution should efficiently handle graphs with up to 100,000 nodes.

Special Values:

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

Constraints:

• The graph will always be a valid directed graph where no node points to itself.

int edgeScore(vector<int>& edges) {
    map<int, long long> mp;
    int n = edges.size();
    int mx = -1, idx = -1;
    for(int i = 0; i < n; i++) {
        mp[edges[i]] += i;
        if(mp[edges[i]] > mx) {
            idx = edges[i];
            mx = mp[edges[i]];
        } else if(mp[edges[i]] == mx) {
            if(edges[i] < idx)
                idx = edges[i];
        }
    }
    return idx;
}

1 : Function Definition

int edgeScore(vector<int>& edges) {

Defines the function `edgeScore` that takes a vector of integers `edges` and returns an integer representing the node with the highest edge score.

2 : Map Initialization

    map<int, long long> mp;

Initializes a map `mp` to store the sum of indices for each node, where the key is the node, and the value is the accumulated score.

3 : Size Calculation

    int n = edges.size();

Stores the size of the `edges` vector in variable `n`.

4 : Variable Initialization

    int mx = -1, idx = -1;

Initializes two variables: `mx` to track the maximum score (initialized to -1) and `idx` to track the node with the highest score (initialized to -1).

5 : Loop Start

    for(int i = 0; i < n; i++) {

Starts a loop to iterate over each element of the `edges` vector.

6 : Update Map

        mp[edges[i]] += i;

Updates the map `mp` by adding the current index `i` to the score of the node represented by `edges[i]`.

7 : Max Score Check

        if(mp[edges[i]] > mx) {

Checks if the current node's score is greater than the maximum score `mx`.

8 : Update Max Score and Node

            idx = edges[i];

If the current node's score is higher, update `idx` to the current node.

9 : Update Max Score

            mx = mp[edges[i]];

Updates the maximum score `mx` to the current node's score.

10 : Tie Breaker

        } else if(mp[edges[i]] == mx) {

Checks if the current node's score is equal to the maximum score, indicating a tie.

11 : Handle Tie

            if(edges[i] < idx)

If the current node is smaller than the previously stored node, update `idx` to the current node.

12 : Update Node in Case of Tie

                idx = edges[i];

Updates the node `idx` to the current node in case of a tie in scores, favoring the smaller node.

13 : Return Statement

    return idx;

Returns the node with the highest score, or the smallest node in case of a tie.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The time complexity is O(n), as we iterate through the `edges` array once, updating the edge scores for each node.

Best Case: O(n)

Worst Case: O(n)

Description: The space complexity is O(n) due to the map storing edge scores for each node.

Leetcode 2374: Node With Highest Edge Score

Explore →