Label Graph Nodes to Maximize Edge Sum

Reported in interviews at Hudson River Trading

Problem statement

You are given an undirected graph with $n$ nodes labeled by index $0, 1, \ldots, n-1$, described by an edge list. You must assign a permutation of the labels $1, 2, \ldots, n$ to the nodes (each node receives exactly one distinct label from $1$ to $n$). The score of an assignment is the sum over every edge $(u, v)$ of $\text{label}[u] + \text{label}[v]$. Return the maximum score achievable over all assignments.

Implement:

def maxEdgeLabelSum(n, edges):
    ...

where n is the number of nodes and edges is a list of [u, v] pairs of node indices (an undirected edge between u and v, with $0 \le u, v < n$). Return a single integer: the maximum possible score. (Return only the maximum score, not the assignment.)

Constraints: $1 \le n \le 10^5$, $0 \le \lvert \text{edges} \rvert \le 2 \cdot 10^5$. The graph may have nodes that touch no edge; such nodes contribute nothing and can be given any leftover label.

Example: n = 5, edges = [[1, 0], [1, 2], [0, 3], [1, 3]]. Node degrees are: node $1$ has degree $3$, node $0$ has degree $2$, node $3$ has degree $2$, node $2$ has degree $1$, node $4$ has degree $0$. Assigning the largest labels to the highest-degree nodes (label $5$ to node $1$, labels $4$ and $3$ to nodes $0$ and $3$, label $2$ to node $2$, label $1$ to node $4$) gives edge sums $(1,0)=5+4=9$, $(1,2)=5+2=7$, $(0,3)=4+3=7$, $(1,3)=5+3=8$, totaling $\mathbf{31}$.

Show hint

Can you rewrite a sum over edges as a sum over nodes, so each node carries its own weight?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems