Node With Highest Edge Score - Leetcode Solution

Problem Statement:

The problem statement is to find the node with the highest edge score in an undirected graph. The edge score of a node is defined as the sum of the weights of all the edges that are connected to that node.

Solution:

To solve this problem, we need to perform the following steps:

1. Create an adjacency list to represent the input graph.
2. Initialize a variable max_edge_score to store the maximum edge score.
3. Initialize a variable max_node to store the node with the maximum edge score.
4. Traverse through each node in the graph and calculate the edge score for each node by taking the sum of the weights of all the edges that are adjacent to that node.
5. If the edge score of the current node is greater than the maximum edge score, set the max_edge_score to the edge score of the current node and update the max_node to the current node.
6. Return the max_node as the node with the highest edge score.

Code:

Here's the python code to solve the Node With Highest Edge Score problem on Leetcode:

from collections import defaultdict

class Solution:
    def findHighestScoreNode(self, edges: List[List[int]], n: int) -> int:
        
        # Create the adjacency list
        graph = defaultdict(list)
        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))
        
        # Initialize the variables
        max_edge_score = 0
        max_node = -1
        
        # Traverse through each node and calculate the edge score
        for node in range(1, n+1):
            edge_score = 0
            for neighbor, weight in graph[node]:
                edge_score += weight
            # Update the max_edge_score and max_node if needed
            if edge_score > max_edge_score:
                max_edge_score = edge_score
                max_node = node
        
        return max_node

Time Complexity:

The time complexity of the solution is O(E+V), where E is the number of edges and V is the number of vertices in the graph.

1