Maximum Path Quality of a Graph - Video Solutions

Problem Overview: You are given an undirected graph where each node has a value and each edge has a travel time. Starting from node 0, you can walk through the graph as long as the total travel time does not exceed maxTime. Nodes may be revisited, but each node’s value is counted only the first time you visit it. The goal is to return the maximum total value collected among all paths that start and end at node 0.

Approach 1: Brute Force Path Enumeration using DFS (Exponential Time, O(V) Space)

The straightforward strategy is to enumerate every valid path that starts at node 0 and does not exceed maxTime. Build an adjacency list for the graph and run a depth-first search. At each step, iterate over all neighbors, subtract the edge travel time, and continue exploring if time remains. Maintain a visited frequency array to track whether a node's value has already been counted. Whenever the DFS returns to node 0, update the global maximum path quality. This approach explores all feasible paths, so the time complexity is exponential in the number of reachable paths, while the recursion stack and visit tracking require O(V) space.

Approach 2: DFS with Backtracking and Value Tracking (Exponential Time with Pruning, O(V) Space)

The practical solution uses DFS with backtracking. Represent the graph using an adjacency list from the graph. During traversal, keep a visit counter array for nodes. When entering a node for the first time (visitCount[node] == 0), add its value to the current score. Recursively explore each neighbor if the remaining time after the edge cost is non‑negative. After returning from recursion, decrement the visit counter to backtrack and restore the previous state. Because revisits are allowed but values count only once, the visit counter is critical. You also update the answer whenever the current node is 0. This search effectively enumerates valid paths but avoids recomputation of path state through careful backtracking. Time complexity remains exponential in the number of feasible paths constrained by maxTime, while space complexity stays O(V) for recursion and tracking.

The algorithm relies heavily on techniques from backtracking and recursive traversal of a graph. Because the time limit restricts path length, the search depth stays manageable for the given constraints.

Recommended for interviews: DFS with backtracking is the expected solution. Interviewers want to see how you model the graph with an adjacency list, track node visits so values are counted once, and correctly restore state during recursion. Brute force path enumeration shows understanding of the problem space, but the backtracking version demonstrates stronger control over recursion and state management.