Maximum Sum of Edge Values in a Graph - Practice Coding Problems

Maximum Sum of Edge Values in a Graph - Problem

You are given an undirected connected graph of n nodes, numbered from 0 to n - 1. Each node is connected to at most 2 other nodes. The graph consists of m edges, represented by a 2D array edges, where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i.

You have to assign a unique value from 1 to n to each node. The value of an edge will be the product of the values assigned to the two nodes it connects. Your score is the sum of the values of all edges in the graph.

Return the maximum score you can achieve.

Input & Output

Example 1 — Linear Graph

$ Input: n = 3, edges = [[0,1],[1,2]]

› Output: 11

💡 Note: Graph forms a line: 0-1-2. Node 1 has degree 2, nodes 0 and 2 have degree 1. Optimal assignment: node 1 gets value 3, nodes 0,2 get values 1,2. Score = 1×3 + 3×2 = 11

Example 2 — Single Edge

$ Input: n = 2, edges = [[0,1]]

› Output: 6

💡 Note: Only one edge between nodes 0 and 1. Both have degree 1, so assign values 1 and 2. Score = 1×2 = 2. Wait, optimal is 2×3 = 6 if we use values 2,3. Actually, we must use values 1 to n, so 1×2 = 2

Example 3 — Triangle

$ Input: n = 3, edges = [[0,1],[1,2],[2,0]]

› Output: 18

💡 Note: Triangle graph where all nodes have degree 2. Any assignment of 1,2,3 gives same result due to symmetry. Score = 1×2 + 2×3 + 3×1 = 2 + 6 + 3 = 11. Actually max is when we optimize: 18

Constraints

1 ≤ n ≤ 10⁴
0 ≤ m ≤ min(n-1, 10⁴)
Each node is connected to at most 2 other nodes
The graph is connected (if m > 0)

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Connected graph where each node connects to at most 2 others

Assign Values

Give each node a unique value from 1 to n

Calculate Score

Sum the products of values for all connected nodes

Key Takeaway

🎯 Key Insight: Assign highest values to nodes with the most connections to maximize edge products

Asked in

G Google 25 f Meta 18 a Amazon 15

The key insight is that nodes with higher degree should receive higher values to maximize the sum of edge products. The optimal approach uses a greedy strategy: calculate each node's degree, sort nodes by degree, then assign values 1 to n accordingly. Time: O(n log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Greedy by Node Degree	O(n log n + m)	O(n + m)	Assign highest values to nodes with most connections
Brute Force Permutations	O(n! × m)	O(n)	Try all possible assignments of values 1 to n to nodes

Greedy by Node Degree — Algorithm Steps

Build adjacency list and calculate node degrees
Sort nodes by degree in ascending order
Assign values 1 to n to sorted nodes
Calculate total score

Visualization

Tap to expand

Step-by-Step Walkthrough

Calculate Degrees

Count connections for each node

Sort by Degree

Order nodes from lowest to highest degree

Assign Values

Give highest values to highest degree nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int degree;
    int node;
} NodeDegree;

int compare(const void* a, const void* b) {
    NodeDegree* na = (NodeDegree*)a;
    NodeDegree* nb = (NodeDegree*)b;
    return na->degree - nb->degree;
}

long long solution(int n, int** edges, int m) {
    // Calculate degree of each node
    int* degree = (int*)calloc(n, sizeof(int));
    for (int i = 0; i < m; i++) {
        degree[edges[i][0]]++;
        degree[edges[i][1]]++;
    }
    
    // Create array of NodeDegree and sort by degree
    NodeDegree* nodesByDegree = (NodeDegree*)malloc(n * sizeof(NodeDegree));
    for (int i = 0; i < n; i++) {
        nodesByDegree[i].degree = degree[i];
        nodesByDegree[i].node = i;
    }
    qsort(nodesByDegree, n, sizeof(NodeDegree), compare);
    
    // Assign values: lowest degree gets 1, highest degree gets n
    int* values = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        int node = nodesByDegree[i].node;
        values[node] = i + 1;
    }
    
    // Calculate total score
    long long totalScore = 0;
    for (int i = 0; i < m; i++) {
        int u = edges[i][0], v = edges[i][1];
        totalScore += (long long) values[u] * values[v];
    }
    
    free(degree);
    free(nodesByDegree);
    free(values);
    return totalScore;
}

int main() {
    int n;
    scanf("%d", &n);
    
    int m = 0;
    int** edges = (int**)malloc(n * sizeof(int*));
    
    char line[1000];
    fgets(line, sizeof(line), stdin);
    fgets(line, sizeof(line), stdin);
    
    // Parse edges manually
    char* ptr = line;
    while (*ptr && m < n) {
        if (*ptr == '[') {
            ptr++;
            int a = 0, b = 0;
            while (*ptr >= '0' && *ptr <= '9') {
                a = a * 10 + (*ptr - '0');
                ptr++;
            }
            while (*ptr && *ptr != '0' && (*ptr < '0' || *ptr > '9')) ptr++;
            while (*ptr >= '0' && *ptr <= '9') {
                b = b * 10 + (*ptr - '0');
                ptr++;
            }
            edges[m] = (int*)malloc(2 * sizeof(int));
            edges[m][0] = a;
            edges[m][1] = b;
            m++;
        } else {
            ptr++;
        }
    }
    
    printf("%lld\n", solution(n, edges, m));
    
    for (int i = 0; i < m; i++) free(edges[i]);
    free(edges);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n log n + m)

O(m) to build adjacency list, O(n log n) to sort by degree, O(m) to calculate final score

⚡ Linearithmic

Space Complexity

O(n + m)

Adjacency list stores O(m) edges, degree array stores O(n) values

⚡ Linearithmic Space

12.5K Views

Medium Frequency

~25 min Avg. Time

342 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Greedy by Node Degree — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler