LeetCode Solutions Blog

Maximum Path Quality of a Graph

Number: 2189

Difficulty: Hard

Paid? No

Problem Description

Given an undirected graph with n nodes (0-indexed) where each node i has an associated value values[i] and each edge is represented by [u, v, time] (indicating that it takes "time" seconds to travel between u and v), find a valid path which starts and ends at node 0, takes at most maxTime seconds, and collects the maximum possible sum of unique node values (each node’s value is counted only once regardless of how many times it is visited).

Key Insights

The problem is solved by exploring all possible paths starting and ending at node 0 with a DFS/backtracking approach.
When revisiting a node, only the first visit contributes its value; subsequent visits do not affect quality.
Precompute the shortest time from every node back to node 0 using Dijkstra’s algorithm to prune DFS paths that cannot possibly return in time.
The graph has a limited number of edges per node (at most 4), keeping the DFS branching factor low even though n can be relatively high.

Space and Time Complexity

Time Complexity: O(2^(n)) in the worst case due to full exploration, but practical constraints (maxTime and degree limits) keep it manageable. Space Complexity: O(n + E) for storing the graph and recursion stack, where E is the number of edges.

Solution

We use a DFS/backtracking strategy to traverse the graph, starting at node 0. Each DFS call tracks the current node, elapsed time, current quality (sum of unique node values visited), and a count array to decide if a node’s value should be added. Before exploring further, we check if the remaining time is at least the minimum time required to return from the current node to 0 (precomputed using Dijkstra). When we return to node 0, we update the result with the highest quality obtained. We construct an adjacency list from the input edges and use recursion with careful backtracking (updating and then undoing changes in the visited array).

Code Solutions

# Python solution with line-by-line comments

import heapq
from collections import defaultdict

def maximumPathQuality(values, edges, maxTime):
    n = len(values)
    
    # Build the graph using an adjacency list: for each node, store (neighbor, time)
    graph = defaultdict(list)
    for u, v, t in edges:
        graph[u].append((v, t))
        graph[v].append((u, t))
    
    # Precompute shortest distances from each node to node 0 using Dijkstra's algorithm for pruning
    minReturnTime = [float('inf')] * n
    minReturnTime[0] = 0
    heap = [(0, 0)]  # (time, node)
    
    while heap:
        curTime, node = heapq.heappop(heap)
        if curTime > minReturnTime[node]:
            continue
        for neighbor, t in graph[node]:
            if curTime + t < minReturnTime[neighbor]:
                minReturnTime[neighbor] = curTime + t
                heapq.heappush(heap, (minReturnTime[neighbor], neighbor))
    
    result = 0
    # visited count to determine if node's value has been collected already
    visitedCount = [0] * n
    
    # DFS function that traverses the graph
    def dfs(node, currentTime, curQuality):
        nonlocal result
        # Only add quality if visiting node 0, ensure always update result
        if node == 0:
            result = max(result, curQuality)
        
        # Explore neighbors if we have enough remaining time to potentially return to 0 (pruning)
        for neighbor, t in graph[node]:
            nextTime = currentTime + t
            if nextTime > maxTime:
                continue
            # Prune if it is impossible to return to node 0 within maxTime even in the best case
            if nextTime + minReturnTime[neighbor] > maxTime:
                continue
            
            # If visiting for the first time, add the value 
            if visitedCount[neighbor] == 0:
                addedValue = values[neighbor]
            else:
                addedValue = 0
            
            visitedCount[neighbor] += 1
            dfs(neighbor, nextTime, curQuality + addedValue)
            visitedCount[neighbor] -= 1  # backtrack

    visitedCount[0] = 1  # starting node is visited
    dfs(0, 0, values[0])
    return result

# For local testing, uncomment below lines:
# values = [0,32,10,43]
# edges = [[0,1,10],[1,2,15],[0,3,10]]
# maxTime = 49
# print(maximumPathQuality(values, edges, maxTime))