Maximum Path Quality of a Graph
HardPrompt
There is an undirected graph with n nodes numbered from 0 to n - 1 (inclusive). You are given a 0-indexed integer array values where values[i] is the value of the ith node. You are also given a 0-indexed 2D integer array edges, where each edges[j] = [uj, vj, timej] indicates that there is an undirected edge between the nodes uj and vj, and it takes timej seconds to travel between the two nodes. Finally, you are given an integer maxTime.
A valid path in the graph is any path that starts at node 0, ends at node 0, and takes at most maxTime seconds to complete. You may visit the same node multiple times. The quality of a valid path is the sum of the values of the unique nodes visited in the path (each node's value is added at most once to the sum).
Return the maximum quality of a valid path.
Note: There are at most four edges connected to each node.
Example 1:
Input: values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 49
Output: 75
Explanation:
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
Explanation:
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
Explanation:
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.length1 <= n <= 10000 <= values[i] <= 1080 <= edges.length <= 2000edges[j].length == 30 <= uj < vj <= n - 110 <= 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.
Approaches
2 approaches with complexity analysis and trade-offs.
This approach significantly improves upon the brute-force DFS by incorporating two key optimizations. First, it maintains the current path's quality incrementally, avoiding costly O(N) recalculations. Second, and more importantly, it uses a powerful pruning strategy. By pre-calculating the shortest time from every node back to node 0 using Dijkstra's algorithm, it can intelligently discard paths that have no chance of returning to the origin within the maxTime limit. This drastically reduces the search space.
Algorithm
- Build an adjacency list
adjfor the graph. - Use Dijkstra's algorithm starting from node 0 to precompute
minTimeToZero[i], the shortest time from every nodeito node 0. - Initialize a global
max_quality = values[0](for the path just staying at 0). - Initialize a frequency array
visited_countsof sizen, withvisited_counts[0] = 1. - Define a recursive function
dfs(u, time_left, visited_counts, current_quality). - In
dfs(u, time_left, ...):- For each neighbor
vofuwith edge timet:- If
time_left >= t:- Pruning Step: Check if
time_left - t >= minTimeToZero[v]. If not, skip this path. - If the check passes, update
visited_countsandnew_quality. - If
v == 0, updatemax_quality = max(max_quality, new_quality). - Make a recursive call:
dfs(v, time_left - t, visited_counts, new_quality). - Backtrack by decrementing
visited_counts[v].
- Pruning Step: Check if
- If
- For each neighbor
- Start the search with
dfs(0, maxTime, visited_counts, values[0]). - Return
max_quality.
Walkthrough
The core idea is to avoid exploring futile paths. A path is futile if, from the current node, there isn't enough time left to return to node 0, even by taking the quickest possible route.
1. Preprocessing with Dijkstra's Algorithm:
We first compute the shortest time from every node in the graph to node 0. Since the graph is undirected and times are non-negative, we can run Dijkstra's algorithm starting from node 0. The result is an array, minTimeToZero, where minTimeToZero[i] stores this minimum time for node i.
2. Optimized DFS with Pruning:
We then perform a DFS, but with a much smarter recursive step. The state of our DFS is (u, timeLeft, visitedCounts, currentQuality).
When at a node u and considering a move to a neighbor v that takes time seconds:
- We first check if we have enough time for this single step:
timeLeft >= time. - Pruning: We then apply our key optimization. The time remaining after moving to
vwould betimeLeft - time. To complete a valid path, we must be able to get fromvback to 0. The fastest this can be done isminTimeToZero[v]. Therefore, we must satisfytimeLeft - time >= minTimeToZero[v]. If this condition fails, we prune this entire branch of the search, as no path extending fromvcan be valid.
If the pruning check passes, we proceed with the recursive call, updating the currentQuality in O(1) time. Whenever a path reaches node 0, we treat it as a valid completed path and update our global maxQuality.
class Solution { int maxQuality = 0; List<int[]>[] adj; int[] values; int[] minTimeToZero; public int maximalPathQuality(int[] values, int[][] edges, int maxTime) { this.values = values; int n = values.length; adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] edge : edges) { adj[edge[0]].add(new int[]{edge[1], edge[2]}); adj[edge[1]].add(new int[]{edge[0], edge[2]}); } minTimeToZero = new int[n]; Arrays.fill(minTimeToZero, Integer.MAX_VALUE); minTimeToZero[0] = 0; PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1])); pq.offer(new int[]{0, 0}); // {node, time} while (!pq.isEmpty()) { int[] curr = pq.poll(); int u = curr[0]; int time = curr[1]; if (time > minTimeToZero[u]) { continue; } for (int[] neighbor : adj[u]) { int v = neighbor[0]; int edgeTime = neighbor[1]; if (minTimeToZero[u] + edgeTime < minTimeToZero[v]) { minTimeToZero[v] = minTimeToZero[u] + edgeTime; pq.offer(new int[]{v, minTimeToZero[v]}); } } } int[] visitedCounts = new int[n]; visitedCounts[0] = 1; this.maxQuality = values[0]; dfs(0, maxTime, visitedCounts, values[0]); return this.maxQuality; } private void dfs(int u, int timeLeft, int[] visitedCounts, int currentQuality) { for (int[] neighbor : adj[u]) { int v = neighbor[0]; int time = neighbor[1]; if (timeLeft >= time) { int newTimeLeft = timeLeft - time; if (newTimeLeft >= minTimeToZero[v]) { boolean isNewlyVisited = (visitedCounts[v] == 0); visitedCounts[v]++; int newQuality = currentQuality + (isNewlyVisited ? values[v] : 0); if (v == 0) { this.maxQuality = Math.max(this.maxQuality, newQuality); } dfs(v, newTimeLeft, visitedCounts, newQuality); visitedCounts[v]--; // Backtrack } } } }}Complexity
Time
O(E log N + B'^D'), where `O(E log N)` is the time for Dijkstra's algorithm. The DFS part is hard to analyze precisely, but the pruning drastically reduces the effective branching factor `B'` and depth `D'` compared to the brute-force approach, making it fast enough for the given constraints.
Space
O(N + E), dominated by the storage for the adjacency list, the `minTimeToZero` array, and data structures for Dijkstra's algorithm. The recursion depth adds a factor but is bounded by the time limit.
Trade-offs
Pros
Significantly more efficient than the brute-force approach due to intelligent pruning.
The O(1) update for path quality avoids the expensive O(N) recalculation.
Effectively solves the problem within the given constraints.
Cons
More complex to implement due to the need for Dijkstra's algorithm as a preprocessing step.
The overhead of Dijkstra's algorithm might be noticeable for graphs where the search space is naturally small.
This approach uses a standard recursive Depth First Search (DFS) to explore all possible paths starting from node 0 that can be completed within maxTime. For every path that ends at node 0, we calculate its quality and update the maximum quality found so far. This method is straightforward but explores a very large search space without any optimizations, making it inefficient.
Algorithm
- Build an adjacency list
adjwhereadj[u]contains pairs of(v, time)for each neighborvofu. - Initialize a global variable
max_quality = 0. - Initialize a frequency array
visited_countsof sizenwith all zeros. - Define a recursive function
dfs(u, time_left, visited_counts). - In
dfs(u, time_left, visited_counts):- Increment
visited_counts[u]. - If
u == 0:- Calculate
current_qualityby summingvalues[i]for alliwherevisited_counts[i] > 0. - Update
max_quality = max(max_quality, current_quality).
- Calculate
- For each neighbor
vofuwith edge timet:- If
time_left >= t, calldfs(v, time_left - t, visited_counts).
- If
- Decrement
visited_counts[u](backtrack).
- Increment
- Start the search with an initial call to
dfs(0, maxTime, visited_counts). - Return
max_quality.
Walkthrough
First, we represent the graph using an adjacency list, where each entry stores a neighbor node and the time to travel to it.
We then initiate a recursive DFS traversal starting from node 0 with the full maxTime available. The state of our recursion is defined by the current node u, the remaining time timeLeft, and a frequency array visitedCounts that tracks how many times each node has been visited in the current path.
Inside the DFS function, we first mark the current node u as visited by incrementing its count. If the current node u is 0, it signifies that we've found a valid path starting and ending at the origin. At this point, we calculate the path's quality by iterating through the visitedCounts array, summing the values of all nodes that have been visited at least once. We then update a global max_quality variable if the current path's quality is higher than what we've found so far.
Next, we iterate through all neighbors v of the current node u. If there is enough time left to travel to a neighbor (timeLeft >= travel_time), we make a recursive call for that neighbor with the updated remaining time. After the recursive calls for all neighbors return, we backtrack by decrementing the visit count for node u, allowing it to be part of other paths.
class Solution { int maxQuality = 0; List<int[]>[] adj; int[] values; public int maximalPathQuality(int[] values, int[][] edges, int maxTime) { this.values = values; int n = values.length; adj = new ArrayList[n]; for (int i = 0; i < n; i++) { adj[i] = new ArrayList<>(); } for (int[] edge : edges) { adj[edge[0]].add(new int[]{edge[1], edge[2]}); adj[edge[1]].add(new int[]{edge[0], edge[2]}); } int[] visitedCounts = new int[n]; dfs(0, maxTime, visitedCounts); return maxQuality; } private void dfs(int u, int timeLeft, int[] visitedCounts) { visitedCounts[u]++; if (u == 0) { int currentQuality = 0; for (int i = 0; i < visitedCounts.length; i++) { if (visitedCounts[i] > 0) { currentQuality += values[i]; } } maxQuality = Math.max(maxQuality, currentQuality); } for (int[] neighbor : adj[u]) { int v = neighbor[0]; int time = neighbor[1]; if (timeLeft >= time) { dfs(v, timeLeft - time, visitedCounts); } } visitedCounts[u]--; // Backtrack }}Complexity
Time
O(B^D * N), where `B` is the maximum branching factor (at most 4), `D` is the maximum path length (bounded by `maxTime / min_edge_time`), and `N` is the number of nodes. The `* N` factor comes from recalculating the quality. Given the constraints, this is roughly `O(4^10 * 1000)`, which is too slow for typical time limits.
Space
O(N + E + D), where N is the number of nodes, E is the number of edges, and D is the maximum recursion depth. This accounts for the adjacency list (O(N+E)), the `visited_counts` array (O(N)), and the recursion stack (O(D), where D is at most `maxTime / min_edge_time`).
Trade-offs
Pros
Simple to understand and implement.
Guaranteed to find the correct answer by exploring all possibilities.
Cons
Highly inefficient due to the exponential number of paths to explore.
The time complexity is prohibitive for the given constraints, likely leading to a 'Time Limit Exceeded' error.
Recalculating the path quality from scratch each time a path reaches node 0 is slow, adding an O(N) factor to each valid path found.
Solutions
Solution
class Solution {private List<int[]>[] g;private boolean[] vis;private int[] values;private int maxTime;private int ans;public int maximalPathQuality(int[] values, int[][] edges, int maxTime) { int n = values.length; g = new List[n]; Arrays.setAll(g, k->new ArrayList<>()); for (var e : edges) { int u = e[0], v = e[1], t = e[2]; g[u].add(new int[]{v, t}); g[v].add(new int[]{u, t}); } vis = new boolean[n]; vis[0] = true; this.values = values; this.maxTime = maxTime; dfs(0, 0, values[0]); return ans; }private void dfs(int u, int cost, int value) { if (u == 0) { ans = Math.max(ans, value); } for (var e : g[u]) { int v = e[0], t = e[1]; 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; } } } }}class Solution {public: int maximalPathQuality(vector<int> &values, vector<vector<int>> &edges, int maxTime) { int n = values.size(); vector<pair<int, int>> g[n]; for (auto &e : edges) { int u = e[0], v = e[1], t = e[2]; g[u].emplace_back(v, t); g[v].emplace_back(u, t); } bool vis[n]; memset(vis, false, sizeof(vis)); vis[0] = true; int ans = 0; auto dfs = [&](auto &&dfs, int u, int cost, int value) -> void { if (u == 0) { ans = max(ans, value); } for (auto &[v, t] : g[u]) { if (cost + t <= maxTime) { if (vis[v]) { dfs(dfs, v, cost + t, value); } else { vis[v] = true; dfs(dfs, v, cost + t, value + values[v]); vis[v] = false; } } } }; dfs(dfs, 0, 0, values[0]); return ans; }};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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.