LeetCode 2538 - Difference Between Maximum and Minimum Price Sum

LeetCode Problem 2538

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Tree, Depth-First Search

Solution

Problem Understanding

We are given an undirected tree with n nodes. Every node has a price value. Since the graph is a tree, there is exactly one simple path between any two nodes.

The problem allows us to choose any node as the root of the tree. After choosing a root, we consider all paths that start from this root and go downward to any node in the tree. Each such path has a price sum, which is the sum of the prices of all nodes on that path.

For a chosen root:

• The maximum price sum is the most expensive root-to-node path.
• The minimum price sum is the cheapest root-to-node path.

The cost of that root is:

$$\text{maximum path sum} - \text{minimum path sum}$$

We must compute the maximum possible cost among all choices of root.

An important observation is that the minimum root-starting path is always just the root itself, because all prices are positive:

$$1 \le price[i]$$

That means extending a path always increases the sum. Therefore:

$$\text{minimum path sum} = price[root]$$

So the problem becomes:

$$\max_{root} (\text{maximum root-to-node path sum} - price[root])$$

Equivalently, for every node, we want the maximum path sum starting from that node and ending anywhere else, excluding the starting node's own contribution from the subtraction.

The constraints are large:

• n <= 10^5
• The graph is a tree, so there are n - 1 edges.

This immediately rules out algorithms that perform DFS or BFS from every node independently, because an O(n^2) solution would time out.

Important edge cases include:

• A tree with only one node.
• A chain-shaped tree, which can create deep recursion and long path sums.
• A star-shaped tree where one node connects to all others.
• Equal price values everywhere.
• Very large price sums, requiring 64-bit integer handling in Go.

Approaches

Brute Force Approach

The brute force method tries every node as the root.

For each root:

1. Run DFS or BFS to compute the maximum path sum starting from that root.
2. Since the minimum path is always the root itself, subtract price[root].
3. Track the global maximum.

This works because it directly follows the definition of the problem.

However, each DFS takes O(n) time, and we perform it for all n nodes:

$$O(n^2)$$

With n = 10^5, this is far too slow.

Key Insight

The important observation is that the answer for a node depends on the best path extending through its neighbors.

This becomes a classic tree dynamic programming and rerooting problem.

For every node, we want to know:

• The best downward path inside its subtree.
• The best path coming from its parent side.

Instead of recomputing everything for every root independently, we can compute reusable DP values.

A particularly elegant formulation keeps two states during DFS:

• A path where the endpoint contributes normally.
• A path where one endpoint is considered "free", meaning we do not count that endpoint's price in the final difference.

While traversing the tree, we combine child contributions and update the answer globally.

The optimal solution uses two DFS passes merged into one recursive transition and runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(n)	Run DFS from every node
Optimal	O(n)	O(n)	Tree DP with rerooting

Algorithm Walkthrough

We build an adjacency list for the tree because trees are sparse graphs and adjacency lists allow efficient traversal.

We perform DFS starting from any node, typically node 0.

During DFS, each node returns two values:

• with_leaf, the maximum path sum starting from this node and ending somewhere below, where the ending node is fully counted.
• without_leaf, the maximum path sum where the ending leaf is excluded from the contribution.

The second state is the crucial trick that models the subtraction of the minimum path.

Step 1: Build the adjacency list

For every edge [u, v]:

• Add v to u's adjacency list.
• Add u to v's adjacency list.

This allows efficient traversal in both directions.

Step 2: Define DFS states

For each node:

• max_with_leaf

Represents the best path sum starting at this node and including all node prices.

• max_without_leaf

Represents the best path sum starting at this node where one endpoint is excluded.

Initially:

$$max_with_leaf = price[node]$$

$$max_without_leaf = 0$$

The second value is zero because a path consisting only of the current node contributes nothing after excluding the leaf.

Step 3: Process children

For every child:

• Recursively compute child states.
• Combine current node states with child states.

Suppose the child returns:

• child_with
• child_without

Then two candidate answers appear:

$$max_with_leaf + child_without$$

and

$$max_without_leaf + child_with$$

These represent combining two complementary path types.

Update the global answer with the maximum of these combinations.

Step 4: Update DP states

We extend the current node's best states using child contributions.

Update:

$$max_with_leaf = \max(max_with_leaf,\ price[node] + child_with)$$

$$max_without_leaf = \max(max_without_leaf,\ price[node] + child_without)$$

Step 5: Return states upward

Return the two updated values to the parent.

Eventually, the global answer contains the maximum possible difference.

Why it works

Every valid answer corresponds to a path where one endpoint contributes fully while the other endpoint is excluded from the subtraction.

The two DP states precisely model these two possibilities. During DFS, every edge is considered once as a connection point between two partial paths. Because the algorithm combines all possible child contributions and propagates optimal states upward, every valid path configuration is examined exactly once.

Therefore, the global maximum computed by the DFS is the optimal answer.

Python Solution

from typing import List
import sys

sys.setrecursionlimit(1 << 20)

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        answer = 0

        def dfs(node: int, parent: int):
            nonlocal answer

            max_with_leaf = price[node]
            max_without_leaf = 0

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                child_with_leaf, child_without_leaf = dfs(neighbor, node)

                answer = max(
                    answer,
                    max_with_leaf + child_without_leaf,
                    max_without_leaf + child_with_leaf,
                )

                max_with_leaf = max(
                    max_with_leaf,
                    price[node] + child_with_leaf
                )

                max_without_leaf = max(
                    max_without_leaf,
                    price[node] + child_without_leaf
                )

            return max_with_leaf, max_without_leaf

        dfs(0, -1)

        return answer

The implementation begins by constructing an adjacency list representation of the tree. Since the graph is undirected, every edge is inserted in both directions.

The DFS function returns two DP values for each node. The first represents the best path sum including all nodes, while the second represents the best path sum where one endpoint is excluded.

For every child, the algorithm first recursively computes the child's states. It then combines those states with the current node's states to update the global answer.

The update formulas ensure that all valid path configurations are explored.

Finally, the DFS returns the best states upward so parent nodes can continue building larger paths.

Go Solution

package main

func maxOutput(n int, edges [][]int, price []int) int64 {
	graph := make([][]int, n)

	for _, edge := range edges {
		u := edge[0]
		v := edge[1]

		graph[u] = append(graph[u], v)
		graph[v] = append(graph[v], u)
	}

	var answer int64 = 0

	var dfs func(int, int) (int64, int64)

	dfs = func(node int, parent int) (int64, int64) {
		maxWithLeaf := int64(price[node])
		var maxWithoutLeaf int64 = 0

		for _, neighbor := range graph[node] {
			if neighbor == parent {
				continue
			}

			childWithLeaf, childWithoutLeaf := dfs(neighbor, node)

			candidate1 := maxWithLeaf + childWithoutLeaf
			candidate2 := maxWithoutLeaf + childWithLeaf

			answer = max64(answer, candidate1)
			answer = max64(answer, candidate2)

			maxWithLeaf = max64(
				maxWithLeaf,
				int64(price[node])+childWithLeaf,
			)

			maxWithoutLeaf = max64(
				maxWithoutLeaf,
				int64(price[node])+childWithoutLeaf,
			)
		}

		return maxWithLeaf, maxWithoutLeaf
	}

	dfs(0, -1)

	return answer
}

func max64(a, b int64) int64 {
	if a > b {
		return a
	}
	return b
}

The Go implementation follows exactly the same DP logic as the Python version.

The main implementation difference is integer handling. Since path sums can become large, the solution uses int64 everywhere for DP values and the final answer.

The DFS is implemented as a recursive closure. The adjacency list uses slices of slices, which is the standard graph representation in Go.

Worked Examples

Example 1

Input:

n = 6
edges = [[0,1],[1,2],[1,3],[3,4],[3,5]]
price = [9,8,7,6,10,5]

Tree structure:

        1
      / | \
     0  2  3
           / \
          4   5

DFS starts at node 0.

Processing leaf nodes

Node	with_leaf	without_leaf
2	7	0
4	10	0
5	5	0

Processing node 3

Initially:

Variable	Value
with_leaf	6
without_leaf	0

After child 4:

Expression	Value
answer	max(0, 6 + 0, 0 + 10) = 10
with_leaf	max(6, 6 + 10) = 16
without_leaf	max(0, 6 + 0) = 6

After child 5:

Expression	Value
answer	max(10, 16 + 0, 6 + 5) = 16
with_leaf	max(16, 6 + 5) = 16
without_leaf	max(6, 6 + 0) = 6

Return from node 3:

(16, 6)

Processing node 1

After combining all children:

Variable	Final Value
with_leaf	24
without_leaf	14
answer	24

Final result:

24

Example 2

Input:

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

Tree:

0 - 1 - 2

At node 2:

with_leaf = 1
without_leaf = 0

At node 1:

Expression	Value
answer	1
with_leaf	2
without_leaf	1

At node 0:

Expression	Value
answer	2
with_leaf	3
without_leaf	2

Final answer:

2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Every node and edge is processed once
Space	O(n)	Adjacency list and recursion stack

The DFS traverses every edge exactly twice, once in each direction. All DP transitions are constant time operations, so the total runtime is linear in the number of nodes.

The adjacency list requires O(n) memory because a tree contains n - 1 edges. The recursion stack can also reach O(n) depth in a skewed tree.

Test Cases

from typing import List

class Solution:
    def maxOutput(self, n: int, edges: List[List[int]], price: List[int]) -> int:
        graph = [[] for _ in range(n)]

        for u, v in edges:
            graph[u].append(v)
            graph[v].append(u)

        answer = 0

        def dfs(node: int, parent: int):
            nonlocal answer

            max_with_leaf = price[node]
            max_without_leaf = 0

            for neighbor in graph[node]:
                if neighbor == parent:
                    continue

                child_with_leaf, child_without_leaf = dfs(neighbor, node)

                answer = max(
                    answer,
                    max_with_leaf + child_without_leaf,
                    max_without_leaf + child_with_leaf,
                )

                max_with_leaf = max(
                    max_with_leaf,
                    price[node] + child_with_leaf
                )

                max_without_leaf = max(
                    max_without_leaf,
                    price[node] + child_without_leaf
                )

            return max_with_leaf, max_without_leaf

        dfs(0, -1)

        return answer

sol = Solution()

assert sol.maxOutput(
    6,
    [[0,1],[1,2],[1,3],[3,4],[3,5]],
    [9,8,7,6,10,5]
) == 24  # official example 1

assert sol.maxOutput(
    3,
    [[0,1],[1,2]],
    [1,1,1]
) == 2  # official example 2

assert sol.maxOutput(
    1,
    [],
    [5]
) == 0  # single node tree

assert sol.maxOutput(
    2,
    [[0,1]],
    [4,9]
) == 9  # simple two-node tree

assert sol.maxOutput(
    4,
    [[0,1],[1,2],[2,3]],
    [1,2,3,4]
) == 9  # chain-shaped tree

assert sol.maxOutput(
    5,
    [[0,1],[0,2],[0,3],[0,4]],
    [10,1,1,1,1]
) == 10  # star-shaped tree

assert sol.maxOutput(
    5,
    [[0,1],[1,2],[1,3],[3,4]],
    [5,5,5,5,5]
) == 15  # equal prices

assert sol.maxOutput(
    7,
    [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]],
    [3,2,4,10,1,6,8]
) == 17  # balanced tree with varied values

Test	Why
Official example 1	Validates complex branching behavior
Official example 2	Validates simple chain
Single node	Ensures base case works
Two-node tree	Smallest nontrivial tree
Chain-shaped tree	Tests deep recursion behavior
Star-shaped tree	Tests high branching factor
Equal prices	Ensures structure, not value variation, drives logic
Balanced mixed tree	General stress scenario

Edge Cases

A single-node tree is the smallest valid input. Since the only path is the node itself, both the maximum and minimum path sums are equal. The correct answer is therefore zero. Many implementations accidentally assume at least one edge exists, but this solution correctly initializes the DFS state so that no invalid transitions occur.

A chain-shaped tree can create recursion depth issues and incorrect DP propagation if parent tracking is mishandled. Since each node has only one child except the ends, the algorithm effectively behaves like dynamic programming on a linked list. The implementation avoids revisiting the parent node, preventing infinite recursion and ensuring each edge is processed once.

A star-shaped tree stresses the merging logic because one central node combines many child contributions. Incorrect implementations sometimes overwrite DP values too early while iterating through children. This solution carefully updates the global answer before modifying the current node's DP states, ensuring every child combination is evaluated correctly.

Another subtle edge case occurs when all node prices are identical. In that situation, the optimal answer depends entirely on path length rather than value distribution. The DP transitions remain correct because they maximize cumulative sums regardless of whether values differ.