#2065

Hard

auto_awesomeBacktracking search with pruning

LeetCode Problem Workspace

Maximum Path Quality of a Graph

Calculate the maximum path quality in a graph using backtracking and pruning to optimize node visits within time limits efficiently.

array backtracking graph

Problem Statement

You are given an undirected graph with n nodes labeled from 0 to n - 1. Each node has a value given in an array values. The graph edges are defined as edges[i] = [u, v, time], representing an undirected edge between u and v that takes time seconds to traverse. A total time limit maxTime is also given.

A valid path starts and ends at node 0 and takes at most maxTime seconds. You may revisit nodes, but the path's quality is the sum of values of unique nodes visited. Your task is to return the maximum possible path quality achievable under these constraints.

Examples

Example 1

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

Output: 75

One possible path is 0 -> 1 -> 0 -> 3 -> 0. The total time taken is 10 + 10 + 10 + 10 = 40 <= 49. The nodes visited are 0, 1, and 3, giving a maximal path quality of 0 + 32 + 43 = 75.

Example 2

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

Output: 25

One possible path is 0 -> 3 -> 0. The total time taken is 10 + 10 = 20 <= 30. The nodes visited are 0 and 3, giving a maximal path quality of 5 + 20 = 25.

Example 3

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

Output: 7

One possible path is 0 -> 1 -> 3 -> 1 -> 0. The total time taken is 10 + 13 + 13 + 10 = 46 <= 50. The nodes visited are 0, 1, and 3, giving a maximal path quality of 1 + 2 + 4 = 7.

Constraints

n == values.length
1 <= n <= 1000
0 <= values[i] <= 108
0 <= edges.length <= 2000
edges[j].length == 3
0 <= uj < vj <= n - 1
10 <= timej, maxTime <= 100
All the pairs [uj, vj] are unique.
There are at most four edges connected to each node.
The graph may not be connected.

Solution Approach

Backtracking with Time Pruning

Recursively explore all paths from node 0, keeping a running sum of unique node values and total time. Abort recursion when accumulated time exceeds maxTime to prune infeasible paths early.

Tracking Unique Node Values

Use a set or boolean array to record nodes visited on the current path. Add node value only once even if revisited, ensuring path quality sums unique node contributions accurately.

Optimizing Path Selection

Prioritize edges leading to unvisited high-value nodes. By combining pruning and selective exploration, reduce redundant searches and improve performance for graphs up to 1000 nodes and 2000 edges.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity can be exponential in the number of nodes due to backtracking, but pruning reduces unnecessary paths. Space complexity is O(n) for visited tracking and recursion stack.

What Interviewers Usually Probe

Emphasize pruning paths exceeding maxTime.
Ask how revisiting nodes affects path quality calculation.
Probe optimization strategies for handling high node counts.

Common Pitfalls or Variants

Common pitfalls

Forgetting to count each node's value only once despite multiple visits.
Not pruning paths early, leading to TLE on dense graphs.
Assuming the graph is connected or all nodes are reachable from node 0.

Follow-up variants

Limit the path to visit each node at most once for stricter constraints.
Change maxTime dynamically and recalculate maximum path quality.
Consider directed edges or weighted node values instead of uniform traversal rules.

FAQ

What does 'Maximum Path Quality of a Graph' mean?

It refers to finding a path that starts and ends at node 0, visits nodes within maxTime, and sums unique node values for the highest total.

Why is backtracking used for this problem?

Backtracking systematically explores all paths while pruning invalid ones, making it ideal to maximize unique node sums without exceeding maxTime.

Can nodes be revisited in the path?

Yes, nodes can be revisited, but their values are counted only once toward path quality.

How does maxTime affect path selection?

maxTime limits the total traversal time, so paths exceeding this value are pruned during backtracking to avoid invalid solutions.

What are common optimization strategies for this problem?

Use pruning based on time limits, prioritize high-value unvisited nodes, and track visited nodes efficiently to reduce redundant exploration.

terminal

Solution

Solution 1: DFS

We observe the data range of the problem and find that the number of edges in each valid path starting from $0$ does not exceed $\frac{\textit{maxTime}}{\min(time_j)} = \frac{100}{10} = 10$, and each node has at most four edges. Therefore, we can directly use naive DFS to brute-force search all valid paths.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

class Solution:
    def maximalPathQuality(
        self, values: List[int], edges: List[List[int]], maxTime: int
    ) -> int:
        def dfs(u: int, cost: int, value: int):
            if u == 0:
                nonlocal ans
                ans = max(ans, value)
            for v, t in g[u]:
                if cost + t <= maxTime:
                    if vis[v]:
                        dfs(v, cost + t, value)
                    else:
                        vis[v] = True
                        dfs(v, cost + t, value + values[v])
                        vis[v] = False

        n = len(values)
        g = [[] for _ in range(n)]
        for u, v, t in edges:
            g[u].append((v, t))
            g[v].append((u, t))
        vis = [False] * n
        vis[0] = True
        ans = 0
        dfs(0, 0, values[0])
        return ans

Continue Practicing

#2056 number of valid move combinations on chessboard #2050 parallel courses iii #2044 count number of maximum bitwise or subsets