Abstract / Summary

Find the difference between the largest and smallest total prices when buying items with given price ranges.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 34% (30k+ submissions).

Typical patterns to solve this problem:

• Array
• Depth First Search
• Dynamic Programming
• Tree

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The provided implementation defines a class Solution with a method maxOutput that computes a maximum value derived from node prices on an undirected tree. The method receives the number of vertices n, a list of edges, and a list of integer prices associated with each vertex. Internally the algorithm builds an adjacency list, then performs a recursive depth-first traversal starting from vertex 0. During the traversal it propagates two aggregates-high and low-that represent the best possible sums when the current node is treated as the upper or lower endpoint of a path. The global variable result is updated whenever a better combination is discovered, and the final maximum is returned.

Key Steps

Build Graph

The first logical block transforms the edge list into an adjacency list named next. For each pair (a, b) the code appends b to a’s neighbor list and vice-versa, establishing a bidirectional connection suitable for tree traversal.

next = [ [] for _ in range(n) ]
for a, b in edges:
    next[a].append(b)
    next[b].append(a)

Depth-First Search

A nested function deeper(node, previous) carries out the recursive exploration. It initializes high with the price of the current node and low with zero, then iterates over all adjacent vertices. The condition if other == previous: continue prevents revisiting the parent node, thereby avoiding infinite recursion on the undirected structure.

Inside the loop the function calls itself on the child other, receiving highMore and lowMore-the best sums that can be achieved deeper in the subtree. The recursion naturally terminates at leaf nodes because their neighbor list contains only the parent, which is filtered out.

def deeper(node, previous):
    high = price[node]
    low  = 0
    for other in next[node]:
        if other == previous:
            continue
        highMore, lowMore = deeper(other, node)
        ...

Result Update

After obtaining the child aggregates, the algorithm evaluates two candidate combinations:

1. Extending a path that ends at the current node with the best “high” value from the child (highMore + low).
2. Extending a path that starts at the current node with the best “low” value from the child (high + lowMore).

The nonlocal result declaration allows the inner function to modify the result variable defined in the outer scope. The max operation records the greatest value seen so far.

nonlocal result
result = max(result, highMore + low, high + lowMore)

Following the update, the aggregates for the current node are refreshed to reflect the possibility of extending the path through the child. high becomes the larger of its current value and the sum of the node’s price with the child’s highMore. Similarly, low is updated with the larger of its current value and the sum of the node’s price with the child’s lowMore.

high = max(high, price[node] + highMore)
low  = max(low,  price[node] + lowMore)

When all neighbors have been processed, the function returns the pair (high, low) to its caller, enabling the parent to incorporate the child’s contributions.

return high, low

The initial call deeper(0, 0) starts the traversal from vertex 0, using a dummy previous value that matches the start node, which effectively prevents any neighbor from being mistakenly skipped at the root.

Final Return

After the recursive exploration completes, the method returns the globally tracked result, which now holds the maximum achievable sum according to the problem’s definition.

return result

Edge Cases Handled

The code gracefully manages several boundary conditions inherent to tree structures. When the tree consists of a single node (n == 1), the adjacency list contains an empty neighbor list, the loop inside deeper never executes, and the function returns the node’s price as high while low remains zero. The global result stays at its initial value of zero because no pair of distinct nodes exists to form a path, which aligns with the expectation that no positive contribution can be derived from a solitary vertex.

For trees where all edges form a straight line (a degenerate chain), the recursion proceeds depth-first along the line, and the high and low values accumulate the sums of contiguous segments. The avoidance of revisiting the parent ensures that each node is visited exactly once, preventing stack overflow due to cycles.

If the price list contains negative values, the initialization of high with price[node] and low with zero allows the algorithm to consider paths that may start or end at a node with a negative contribution, while still permitting the selection of an empty segment (low == 0) when extending a path would decrease the total. This implicit handling of negative prices ensures that the maximum result never deteriorates because of an unfavorable segment.

When multiple children are attached to a node, the code evaluates each child independently, updating high and low after each iteration. This sequential processing captures the best possible extension from any single child while preserving the best combination across different subtrees through the global result update.

Performance Optimizations

The algorithm leverages the tree’s acyclic nature to achieve a single pass over all vertices. By constructing an adjacency list, neighbor lookup occurs in constant time per edge, and the recursive depth-first search visits each node exactly once, eliminating redundant traversals.

The use of two aggregates (high and low) per node condenses the necessary information into constant-size tuples, avoiding the allocation of larger intermediate structures. Updating high and low in place reduces memory churn and keeps the recursion stack depth proportional to the tree height.

The nonlocal result pattern eliminates the need to propagate the best global value up the call stack, allowing immediate comparison and update at each node. This direct approach avoids additional passes that would otherwise be required to aggregate results after the recursion completes.

By initializing low to zero rather than a sentinel value, the code sidesteps extra conditional checks when combining path segments, streamlining the arithmetic involved in the max operations. The early continue for the parent node prevents unnecessary recursive calls, ensuring that the algorithm’s work is bounded by the number of edges rather than the square of the node count.

Imagine a big playground with many shiny lanterns connected by ropes. Each lantern has a different number written on it to show how bright it is. You start at one lantern and follow the ropes to visit others, but you have to be careful never to step on the same rope twice because that would be like walking in circles.

The code works like a little explorer running through this playground. It builds a map so it knows which lanterns are connected to each other. Once the map is ready, it starts exploring from the very first lantern.

As the explorer moves along the ropes, it keeps track of two special values for every path it travels. One value keeps adding up the brightness of all the lanterns along the way to find the biggest possible shine. The other value looks for paths where some lanterns are turned off, which helps find different patterns of light.

At every single lantern, the code pauses to look at the paths it has already checked. It compares the brightness it just found with the brightest path it has seen before. If the new path is even brighter, it remembers that instead. The explorer keeps jumping from rope to rope, always comparing and remembering the very best way to light up the path until it has traveled across the whole playground.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java	Go	Python
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality