LeetCode 2065 - Maximum Path Quality of a Graph

LeetCode Problem 2065

Difficulty: 🔴 Hard
Topics: Array, Backtracking, Graph Theory

Solution

Problem Understanding

We are given an undirected weighted graph where each node has an associated value. A path is considered valid if:

1. It starts at node 0
2. It ends at node 0
3. The total travel time does not exceed maxTime

The important detail is that nodes may be revisited multiple times, but each node's value contributes to the path quality only once.

The goal is to find the maximum possible path quality among all valid paths.

The input consists of:

• values[i], the value assigned to node i
• edges[j] = [u, v, t], representing an undirected edge between nodes u and v with travel time t
• maxTime, the maximum total travel time allowed

The graph can contain cycles, and revisiting nodes is allowed. Since we only count unique node values once, we must carefully track whether a node has already contributed to the total score.

The constraints provide several important observations:

• maxTime <= 100
• Every edge has weight at least 10
• Each node has degree at most 4

These constraints are extremely important. Even though the graph may contain up to 1000 nodes, the maximum path length is naturally limited because every edge traversal costs at least 10. That means any valid path can contain at most about 10 edge traversals.

This makes exhaustive depth first search feasible.

Several edge cases are important:

• The graph may be disconnected
• Some nodes may never be reachable within maxTime
• The optimal path may revisit nodes many times
• Returning to node 0 is mandatory
• A path that exceeds maxTime is invalid even if it has high value
• Node 0 may have value 0, but it still counts as visited

Approaches

Brute Force Approach

The brute force idea is to generate every possible path starting from node 0, track the elapsed time, and whenever we return to node 0, update the answer with the total unique-node value collected.

For each recursive step:

• Try every neighboring node
• Add travel time
• Continue exploring if the time limit is not exceeded
• Maintain a set of visited nodes to avoid double counting node values

This approach is correct because it explores every valid path.

However, naive brute force becomes extremely expensive because the graph may contain cycles, meaning the number of possible paths grows exponentially with path length.

Without careful pruning and exploitation of the small maxTime, this approach would be too slow in general graphs.

Key Insight

The crucial observation is that maxTime is very small.

Since every edge requires at least 10 seconds:

• The maximum recursion depth is bounded
• Each node has at most 4 neighbors
• The effective search space becomes manageable

This allows us to use depth first search with backtracking.

We maintain:

• Current node
• Current elapsed time
• Current accumulated quality
• Frequency count of visited nodes

The frequency count is important because revisiting nodes is allowed. We only add a node's value the first time it appears in the current path.

Whenever the DFS returns to node 0, we update the global answer.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(path length)	Explores all possible paths without exploiting constraints
Optimal DFS + Backtracking	O(4^(maxTime/10))	O(n + maxTime/10)	Feasible because depth is naturally bounded

Algorithm Walkthrough

1. Build an adjacency list for the graph.

Since the graph is undirected, each edge is inserted in both directions. The adjacency list allows efficient traversal of neighboring nodes. 2. Initialize a frequency array.

We use visited_count[node] to track how many times a node appears in the current path.

This is better than a boolean visited array because revisiting nodes is allowed. 3. Start DFS from node 0.

Initially:

• Current node = 0
• Current time = 0
• Current quality = values[0]

4. At each DFS state, check whether the current node is 0.

If so, the current path is valid because:

• It started at 0
• It currently ends at 0
• Time is already guaranteed to be within the limit

Update the global answer. 5. Explore all neighboring nodes.

For each neighbor:

• Compute the new elapsed time
• Skip the move if it exceeds maxTime

6. Determine whether the neighbor contributes new value.

If visited_count[neighbor] == 0, this is the first visit in the current path, so add values[neighbor].

Otherwise, add nothing. 7. Apply the move.

Increment:

• visited_count[neighbor]
• current quality if appropriate

8. Recurse into the neighbor.

Continue exploring deeper paths. 9. Backtrack after recursion.

Decrement visited_count[neighbor] so the state is restored correctly for other DFS branches.

Why it works

The DFS explores every valid path whose total time does not exceed maxTime. Since every recursive state fully represents the current path configuration, and backtracking restores the previous state correctly, every feasible path is examined exactly as needed.

The frequency tracking guarantees that each node contributes its value at most once per path, which matches the problem definition.

Because the answer is updated whenever we return to node 0, the algorithm considers all valid paths and therefore finds the maximum possible quality.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        graph = defaultdict(list)

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

        n = len(values)
        visited_count = [0] * n

        answer = values[0]
        visited_count[0] = 1

        def dfs(node: int, current_time: int, current_quality: int) -> None:
            nonlocal answer

            if node == 0:
                answer = max(answer, current_quality)

            for neighbor, travel_time in graph[node]:
                next_time = current_time + travel_time

                if next_time > maxTime:
                    continue

                first_visit = visited_count[neighbor] == 0

                visited_count[neighbor] += 1

                added_value = values[neighbor] if first_visit else 0

                dfs(
                    neighbor,
                    next_time,
                    current_quality + added_value
                )

                visited_count[neighbor] -= 1

        dfs(0, 0, values[0])

        return answer

The implementation begins by constructing the adjacency list representation of the graph. Since the graph is undirected, each edge is added in both directions.

The visited_count array tracks how many times each node appears in the current DFS path. This is essential because revisiting nodes is allowed, but node values should only be counted once.

The DFS function maintains three pieces of state:

• Current node
• Elapsed time
• Current quality

Whenever the DFS reaches node 0, the current path is valid, so we update the answer.

For each neighboring node, we first check whether taking that edge would exceed maxTime. If it does, we skip that branch immediately.

The variable first_visit determines whether the node's value should be added to the quality. After recursion completes, we decrement the visit count to restore the previous state for backtracking.

Go Solution

package main

func maximalPathQuality(values []int, edges [][]int, maxTime int) int {
	type Edge struct {
		to   int
		time int
	}

	n := len(values)

	graph := make([][]Edge, n)

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

		graph[u] = append(graph[u], Edge{v, t})
		graph[v] = append(graph[v], Edge{u, t})
	}

	visitedCount := make([]int, n)

	answer := values[0]
	visitedCount[0] = 1

	var dfs func(node int, currentTime int, currentQuality int)

	dfs = func(node int, currentTime int, currentQuality int) {
		if node == 0 && currentQuality > answer {
			answer = currentQuality
		}

		for _, edge := range graph[node] {
			nextNode := edge.to
			nextTime := currentTime + edge.time

			if nextTime > maxTime {
				continue
			}

			firstVisit := visitedCount[nextNode] == 0

			visitedCount[nextNode]++

			addedValue := 0
			if firstVisit {
				addedValue = values[nextNode]
			}

			dfs(
				nextNode,
				nextTime,
				currentQuality+addedValue,
			)

			visitedCount[nextNode]--
		}
	}

	dfs(0, 0, values[0])

	return answer
}

The Go implementation follows the same DFS and backtracking strategy as the Python version.

Several Go-specific details are worth noting:

• A custom Edge struct is used for adjacency lists
• Slices are used instead of dynamic Python lists
• The recursive DFS is declared as a function variable so it can recursively reference itself
• Integer overflow is not a concern because the maximum possible quality fits comfortably within Go's integer range

Worked Examples

Example 1

values = [0,32,10,43]
edges = [[0,1,10],[1,2,15],[0,3,10]]
maxTime = 49

Graph

0 --10-- 1 --15-- 2
|
10
|
3

DFS Trace

Step	Path	Time	Unique Nodes	Quality
1	0	0	{0}	0
2	0 → 1	10	{0,1}	32
3	0 → 1 → 0	20	{0,1}	32
4	0 → 1 → 0 → 3	30	{0,1,3}	75
5	0 → 1 → 0 → 3 → 0	40	{0,1,3}	75

At step 5 we are back at node 0, so the answer becomes 75.

Trying to include node 2 would exceed the available time budget while still needing to return to node 0.

Final answer:

75

Example 2

values = [5,10,15,20]
edges = [[0,1,10],[1,2,10],[0,3,10]]
maxTime = 30

DFS Trace

Step	Path	Time	Unique Nodes	Quality
1	0	0	{0}	5
2	0 → 3	10	{0,3}	25
3	0 → 3 → 0	20	{0,3}	25

Path 0 → 1 → 2 cannot return to 0 within time.

Final answer:

25

Example 3

values = [1,2,3,4]
edges = [[0,1,10],[1,2,11],[2,3,12],[1,3,13]]
maxTime = 50

DFS Trace

Step	Path	Time	Unique Nodes	Quality
1	0	0	{0}	1
2	0 → 1	10	{0,1}	3
3	0 → 1 → 3	23	{0,1,3}	7
4	0 → 1 → 3 → 1	36	{0,1,3}	7
5	0 → 1 → 3 → 1 → 0	46	{0,1,3}	7

Final answer:

7

Complexity Analysis

Measure	Complexity	Explanation
Time	O(4^(maxTime / 10))	Each node has at most 4 neighbors and recursion depth is bounded
Space	O(n + maxTime / 10)	Adjacency list plus recursion stack and visit tracking

The branching factor is at most 4 because each node has degree at most 4.

Since every edge costs at least 10, the maximum recursion depth is approximately:

$\frac{maxTime}{10}$

Therefore the total number of explored states is bounded by:

$4^{\frac{maxTime}{10}}$

With maxTime <= 100, this search space is manageable in practice.

Test Cases

from typing import List
from collections import defaultdict

class Solution:
    def maximalPathQuality(self, values: List[int], edges: List[List[int]], maxTime: int) -> int:
        graph = defaultdict(list)

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

        n = len(values)
        visited_count = [0] * n

        answer = values[0]
        visited_count[0] = 1

        def dfs(node: int, current_time: int, current_quality: int) -> None:
            nonlocal answer

            if node == 0:
                answer = max(answer, current_quality)

            for neighbor, travel_time in graph[node]:
                next_time = current_time + travel_time

                if next_time > maxTime:
                    continue

                first_visit = visited_count[neighbor] == 0

                visited_count[neighbor] += 1

                added_value = values[neighbor] if first_visit else 0

                dfs(
                    neighbor,
                    next_time,
                    current_quality + added_value
                )

                visited_count[neighbor] -= 1

        dfs(0, 0, values[0])

        return answer

solution = Solution()

# Example 1
assert solution.maximalPathQuality(
    [0,32,10,43],
    [[0,1,10],[1,2,15],[0,3,10]],
    49
) == 75

# Example 2
assert solution.maximalPathQuality(
    [5,10,15,20],
    [[0,1,10],[1,2,10],[0,3,10]],
    30
) == 25

# Example 3
assert solution.maximalPathQuality(
    [1,2,3,4],
    [[0,1,10],[1,2,11],[2,3,12],[1,3,13]],
    50
) == 7

# Single node graph
assert solution.maximalPathQuality(
    [100],
    [],
    10
) == 100

# Cannot travel anywhere and return
assert solution.maximalPathQuality(
    [5,20],
    [[0,1,15]],
    20
) == 5

# Revisiting nodes multiple times
assert solution.maximalPathQuality(
    [1,2,3],
    [[0,1,10],[1,2,10]],
    40
) == 6

# Graph with disconnected component
assert solution.maximalPathQuality(
    [1,50,100],
    [[0,1,10]],
    30
) == 51

# Zero value nodes
assert solution.maximalPathQuality(
    [0,0,10],
    [[0,1,10],[1,2,10]],
    40
) == 10

# Tight time budget
assert solution.maximalPathQuality(
    [5,6,7],
    [[0,1,10],[1,2,10]],
    20
) == 11

Test	Why
Example 1	Standard branching graph
Example 2	Best path avoids deeper branch
Example 3	Revisiting nodes required
Single node graph	Smallest possible input
Cannot travel anywhere and return	Return-to-zero constraint
Revisiting nodes multiple times	Ensures duplicate values are not double counted
Graph with disconnected component	Unreachable nodes ignored
Zero value nodes	Handles nodes contributing zero
Tight time budget	Verifies pruning logic

Edge Cases

Single Node Graph

If the graph contains only node 0, the algorithm should immediately return values[0].

This can easily cause bugs if the implementation assumes edges always exist or only updates the answer during traversal. Our solution correctly initializes the answer with values[0] before DFS begins.

Revisiting Nodes

A major source of bugs is double counting node values.

For example, a path like:

0 → 1 → 0 → 1 → 0

should only count node 1 once.

Using a frequency array instead of a boolean visited array allows revisiting while still ensuring values are only added during the first visit.

Paths That Cannot Return to Node 0

Some paths may collect large value totals but fail to return to node 0 within the time limit.

A naive implementation might incorrectly count such paths.

Our algorithm only updates the answer when the current node is exactly 0, ensuring every recorded solution is valid according to the problem definition.