LeetCode 3547 - Maximum Sum of Edge Values in a Graph

LeetCode Problem 3547

Difficulty: 🔴 Hard
Topics: Math, Greedy, Graph Theory

Solution

Problem Understanding

The graph is undirected, connected, and every node has degree at most 2.

A connected graph where every node has degree at most 2 can only have one of two shapes:

• A simple path, containing exactly n - 1 edges.
• A simple cycle, containing exactly n edges.

We must assign the numbers 1 through n to the nodes, using each number exactly once.

For every edge (u, v), its contribution to the score is:

$$value(u) \times value(v)$$

The goal is to maximize the sum of all edge contributions.

The constraints are large, n can be as large as 5 * 10^4, so any solution that explicitly tries many assignments is impossible. We need to exploit the special structure of the graph.

An important observation is that the actual node labels do not matter. Since the graph is guaranteed to be either a path or a cycle, the answer depends only on:

• n
• whether the graph is a path or a cycle

The particular numbering of vertices in edges is irrelevant.

Some important edge cases are:

• n = 1, where there are no edges and the answer is 0.
• Very long paths, where an O(n!) assignment search is impossible.
• Cycles, where every vertex has degree 2.
• Paths, where exactly two vertices have degree 1.

Approaches

Brute Force

A brute force solution would try every permutation of the values 1...n.

For each permutation, we would compute the sum of the products on all edges and keep the maximum.

This is correct because it examines every possible assignment.

However, there are n! assignments. Even for n = 15, this is already completely infeasible. The actual constraint is 5 * 10^4, making brute force impossible.

Key Insight

Because the graph is either a path or a cycle, we can view the assigned values as being arranged along a line or around a circle.

Let:

$$Q=\sum_{i=1}^{n} i^2$$

which is fixed regardless of the assignment.

For a cycle arrangement $a_1,a_2,\dots,a_n$,

$$\sum (a_i-a_{i+1})^2 = 2Q - 2\sum a_i a_{i+1}$$

where $a_{n+1}=a_1$.

Therefore,

$$\sum a_i a_{i+1} = Q-\frac{D}{2}$$

where

$$D=\sum (a_i-a_{i+1})^2$$

Maximizing the score is equivalent to minimizing the sum of squared adjacent differences.

The optimal arrangement is the classical pendulum arrangement:

$$1,2,4,6,\dots,5,3$$

or its symmetric variants.

In this arrangement:

• two adjacent differences are 1
• all remaining adjacent differences are 2

Therefore

$$D_{\text{cycle}} = 2\cdot 1^2 + (n-2)\cdot 2^2 = 4n-6$$

Hence

$$\text{Cycle Answer} = Q-(2n-3)$$

For a path, a similar derivation yields

$$\text{Path Answer} = Q-(2n-1)$$

Thus we never need to construct the assignment itself. We only need to determine whether the graph is a path or a cycle.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * m)	O(n)	Tries every assignment
Optimal	O(n)	O(1)	Uses the path/cycle structure and a closed form

Algorithm Walkthrough

1. Compute

$$Q=\frac{n(n+1)(2n+1)}{6}$$

This is the sum of squares from 1 to n. 2. Determine whether the graph is a path or a cycle.

Since the graph is connected and every vertex has degree at most 2:

• A cycle has exactly n edges.
• A path has exactly n - 1 edges.

3. If m == n, the graph is a cycle. Return

$$Q-(2n-3)$$ 4. Otherwise the graph is a path. Return

$$Q-(2n-1)$$ 5. Handle n = 1 naturally. The formula produces 0.

Why it works

The sum of squares of the assigned values is fixed. Therefore maximizing the sum of adjacent products is equivalent to minimizing the sum of squared differences between adjacent assigned values.

For both paths and cycles, the optimal ordering is the pendulum ordering, which minimizes these squared differences. The resulting minimum values are:

$$D_{\text{cycle}}=4n-6$$

and

$$D_{\text{path}}=4n-7$$

Substituting these minima into the algebraic identities relating adjacent products and adjacent squared differences yields the closed forms:

$$Q-(2n-3)$$

for cycles and

$$Q-(2n-1)$$

for paths.

Therefore the formulas always produce the maximum possible score. We are asked to assign unique values from 1 to n to the nodes of an undirected connected graph where each node has at most two neighbors. Each edge's value is the product of the values assigned to its two endpoints. The task is to maximize the sum of all edge values.

Restating in simpler terms, imagine the graph as a collection of nodes connected by edges. Each node must get a distinct integer from 1 to n. The "score" of the graph is the sum of the product of node values along each edge. We want the maximum possible score.

The input consists of:

• An integer n representing the number of nodes.
• A list edges where each element [a_i, b_i] represents an undirected edge between nodes a_i and b_i.

The output is a single integer: the maximum sum of edge products achievable by assigning values 1 through n to the nodes uniquely.

Constraints indicate:

• The graph is connected, so every node is reachable.
• Each node has degree ≤ 2, implying the graph is a collection of paths and cycles.
• 1 <= n <= 5 * 10^4, so brute-force enumeration of all permutations is infeasible.
• m == edges.length <= n guarantees the graph is sparse.

Edge cases include:

• A single node (n = 1) has no edges.
• A linear path (degree ≤ 2) where extreme values at ends maximize products.
• A cycle where assigning values optimally around the cycle may require careful ordering.

Approaches

Brute Force Approach: Enumerate all n! permutations of node values, calculate the edge product sum for each, and select the maximum. This is correct because it evaluates every possible assignment. However, it is infeasible for n up to 50,000 due to factorial complexity.

Key Observation for Optimal Approach: Each node has at most two neighbors, so the graph is composed of paths or cycles. To maximize the sum of products:

1. Nodes with higher degrees should be assigned higher values to maximize their contribution to multiple edges.
2. Since each node's degree is at most 2, degree 2 nodes are more "valuable" than degree 1 nodes, and degree 1 nodes least valuable.
3. Sorting nodes by degree and assigning the largest values to nodes with highest degree achieves the optimal score.

This reduces the problem to:

• Counting the degree of each node.
• Sorting nodes by degree.
• Assigning the largest numbers from n down to 1 based on degree.
• Summing the product of assigned values along edges.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n! * m)	O(n)	Enumerate all permutations; infeasible for n > 10
Optimal	O(n log n + m)	O(n + m)	Sort nodes by degree and assign values greedily; exploits graph sparsity and degree ≤ 2

Algorithm Walkthrough

1. Initialize an array degree of size n to count the degree of each node.
2. For each edge [u, v] in edges, increment degree[u] and degree[v].
3. Create a list of node indices nodes = [0, 1, ..., n-1].
4. Sort nodes in descending order of degree. Nodes with higher degrees will be assigned higher values.
5. Create an array assigned of size n to store assigned values.
6. Assign the values from n down to 1 to the nodes in sorted order.
7. Initialize total_score = 0.
8. For each edge [u, v], add assigned[u] * assigned[v] to total_score.
9. Return total_score.

Why it works: Each node contributes to degree[node] edges. By assigning higher numbers to higher-degree nodes, we maximize each product. Since each node has at most two neighbors, this local greedy choice leads to a globally optimal solution.

Python Solution

from typing import List

class Solution:
    def maxScore(self, n: int, edges: List[List[int]]) -> int:
        q = n * (n + 1) * (2 * n + 1) // 6
        m = len(edges)

        if m == n:  # cycle
            return q - (2 * n - 3)

        return q - (2 * n - 1)  # path

The implementation is extremely small because all of the heavy work is done by the mathematical derivation.

First, it computes the sum of squares Q. Then it determines the graph type by counting edges. A connected graph with maximum degree 2 is a cycle exactly when it has n edges. Otherwise it must be a path.

Finally, it applies the corresponding closed-form formula and returns the result. # Step 1: Count degrees degree = [0] * n for u, v in edges: degree[u] += 1 degree[v] += 1

    # Step 2: Sort nodes by degree descending
    nodes = list(range(n))
    nodes.sort(key=lambda x: degree[x], reverse=True)
    
    # Step 3: Assign values from n down to 1
    assigned = [0] * n
    value = n
    for node in nodes:
        assigned[node] = value
        value -= 1
    
    # Step 4: Compute total score
    total_score = 0
    for u, v in edges:
        total_score += assigned[u] * assigned[v]
    
    return total_score

The implementation first computes degrees, then sorts nodes by degree to prioritize high-value assignments. Values are assigned greedily, and edge products are summed to return the maximum score.

## Go Solution

```go
func maxScore(n int, edges [][]int) int64 {
	q := int64(n) * int64(n+1) * int64(2*n+1) / 6
	m := len(edges)

	if m == n { // cycle
		return q - int64(2*n-3)
	}

	return q - int64(2*n-1) // path
}

The Go solution follows exactly the same logic as the Python solution.

The only notable difference is that int64 is used throughout the computation. For n = 5 * 10^4, the answer is on the order of n^3, so using 64-bit integers avoids overflow.

Worked Examples

Example 1

Input:

n = 4
edges = [[0,1],[1,2],[2,3]]

The graph has:

m = 3
n = 4

Since m = n - 1, the graph is a path.

Compute:

Quantity	Value
Q	1² + 2² + 3² + 4² = 30
Penalty	2n - 1 = 7
Answer	30 - 7 = 23

Result:

23

Example 2

Input:

n = 6
edges = [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]

The graph has:

m = 6
n = 6

Since m = n, the graph is a cycle.

Compute:

Quantity	Value
Q	1² + 2² + 3² + 4² + 5² + 6² = 91
Penalty	2n - 3 = 9
Answer	91 - 9 = 82

Result:

82

degree := make([]int, n)
for _, e := range edges {
    u, v := e[0], e[1]
    degree[u]++
    degree[v]++
}

nodes := make([]int, n)
for i := 0; i < n; i++ {
    nodes[i] = i
}

// Sort nodes by degree descending
sort.Slice(nodes, func(i, j int) bool {
    return degree[nodes[i]] > degree[nodes[j]]
})

assigned := make([]int64, n)
value := int64(n)
for _, node := range nodes {
    assigned[node] = value
    value--
}

var totalScore int64 = 0
for _, e := range edges {
    u, v := e[0], e[1]
    totalScore += assigned[u] * assigned[v]
}

return totalScore

}

The Go implementation mirrors Python: degree array, node sorting by degree, greedy value assignment, and summing edge products. `int64` is used to avoid overflow for large `n`.

## Worked Examples

**Example 1:**

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

| Node | Degree | Assigned |
| --- | --- | --- |
| 1 | 2 | 4 |
| 2 | 2 | 3 |
| 0 | 1 | 2 |
| 3 | 1 | 1 |

Edge sums:

- Edge [0,1] → 2 * 4 = 8
- Edge [1,2] → 4 * 3 = 12
- Edge [2,3] → 3 * 1 = 3

Total = 8 + 12 + 3 = 23

**Example 2:**

Input: `n = 6, edges = [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]`

Degree counts:

- Node 0: 2
- Node 1: 2
- Node 2: 2
- Node 3: 2
- Node 4: 2
- Node 5: 2

Assign values descending from 6 arbitrarily as all have same degree. Compute edge products to achieve total 82.

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O(1) | Only a few arithmetic operations are performed |
| Space | O(1) | No auxiliary data structures are required |

The graph itself is not traversed. The solution only uses the number of vertices and the number of edges. Consequently both time and space usage are constant.

## Test Cases

```python
from typing import List

s = Solution()

assert s.maxScore(1, []) == 0  # single node

assert s.maxScore(
    4,
    [[0, 1], [1, 2], [2, 3]]
) == 23  # example 1

assert s.maxScore(
    6,
    [[0, 3], [4, 5], [2, 0], [1, 3], [2, 4], [1, 5]]
) == 82  # example 2

assert s.maxScore(
    2,
    [[0, 1]]
) == 2  # smallest path

assert s.maxScore(
    3,
    [[0, 1], [1, 2]]
) == 9  # path of length 2

assert s.maxScore(
    3,
    [[0, 1], [1, 2], [2, 0]]
) == 11  # smallest cycle

assert s.maxScore(
    4,
    [[0, 1], [1, 2], [2, 3], [3, 0]]
) == 25  # cycle of 4 nodes

assert s.maxScore(
    5,
    [[0, 1], [1, 2], [2, 3], [3, 4]]
) == 46  # larger path

assert s.maxScore(
    5,
    [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]]
) == 48  # larger cycle

Test Summary

Test	Why
n=1	No edges exist
Example 1	Verifies path formula
Example 2	Verifies cycle formula
Smallest path	Minimum nontrivial path
Path with 3 nodes	Simple path validation
Smallest cycle	Minimum cycle validation
Cycle with 4 nodes	Checks cycle formula further
Path with 5 nodes	Larger path case
Cycle with 5 nodes	Larger cycle case

Edge Cases

Single Node

When n = 1, the graph contains no edges. A buggy implementation might incorrectly apply path or cycle logic without considering that the score must be zero. The formula naturally evaluates to zero because the sum of squares is 1 and the path expression becomes 1 - 1 = 0.

Distinguishing Path vs Cycle

A common mistake is to inspect vertex degrees explicitly. While that works, it is unnecessary. Because the graph is connected and every degree is at most 2, the graph is a cycle if and only if it has exactly n edges. The implementation uses this simpler and more robust criterion.

Large Values of n

For n = 50,000, the answer is roughly proportional to n^3. Using 32-bit integers would overflow. The Go implementation uses int64, and Python integers automatically support arbitrary precision, ensuring correct results for the largest inputs. | Time | O(n log n + m) | Sorting nodes dominates; counting degrees is O(m) | | Space | O(n + m) | Arrays for degrees, assignments, and storing edges |

Sorting dominates because each node must be considered once. Edge iteration is linear in m, which is ≤ n.

Test Cases

# Provided examples
assert Solution().maxScore(4, [[0,1],[1,2],[2,3]]) == 23  # linear path
assert Solution().maxScore(6, [[0,3],[4,5],[2,0],[1,3],[2,4],[1,5]]) == 82  # complex connections

# Edge cases
assert Solution().maxScore(1, []) == 0  # single node, no edges
assert Solution().maxScore(2, [[0,1]]) == 2  # two nodes, max product is 1*2 = 2
assert Solution().maxScore(3, [[0,1],[1,2]]) == 5  # path of length 2

# Cycle
assert Solution().maxScore(4, [[0,1],[1,2],[2,3],[3,0]]) == 30  # assign largest numbers to maximize product sum

Test	Why
Single node	Handles no edges
Two nodes	Minimal graph with one edge
Path length 2	Simple linear path
Cycle of length 4	Verify cycle handling

Edge Cases

1. Single Node: If n=1, there are no edges. The algorithm handles this because the edge iteration loop is skipped, returning 0.

2. Linear Path: For a path like [0,1,2,...], the highest values should