# Maximum Path Quality of a Graph
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximum-path-quality-of-a-graph)
Canonical: https://scaleengineer.com/dsa/problems/maximum-path-quality-of-a-graph
**Patterns:** [Backtracking](https://scaleengineer.com/dsa/patterns/backtracking)
**Data structures:** Array, Graph
**Companies:** [Atlassian](https://scaleengineer.com/companies/atlassian), [DoorDash](https://scaleengineer.com/companies/doordash), [SAP](https://scaleengineer.com/companies/sap)
---
## Problem
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:**

![](https://assets.glich.co/dsa/maximum-path-quality-of-a-graph/image0.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-path-quality-of-a-graph/image1.png) 

**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:**

![](https://assets.glich.co/dsa/maximum-path-quality-of-a-graph/image2.png) 

**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.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.

# Approaches
## Brute-Force Depth First Search
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.
**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`).
**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.
### Explanation
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.

```java
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
    }
}
```
### Algorithm
*   Build an adjacency list `adj` where `adj[u]` contains pairs of `(v, time)` for each neighbor `v` of `u`.
*   Initialize a global variable `max_quality = 0`.
*   Initialize a frequency array `visited_counts` of size `n` with 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_quality` by summing `values[i]` for all `i` where `visited_counts[i] > 0`.
        *   Update `max_quality = max(max_quality, current_quality)`.
    *   For each neighbor `v` of `u` with edge time `t`:
        *   If `time_left >= t`, call `dfs(v, time_left - t, visited_counts)`.
    *   Decrement `visited_counts[u]` (backtrack).
*   Start the search with an initial call to `dfs(0, maxTime, visited_counts)`.
*   Return `max_quality`.

## Optimized DFS with Pruning via Dijkstra's Algorithm
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.
**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.
**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.
### Explanation
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 `v` would be `timeLeft - time`. To complete a valid path, we must be able to get from `v` back to 0. The fastest this can be done is `minTimeToZero[v]`. Therefore, we must satisfy `timeLeft - time >= minTimeToZero[v]`. If this condition fails, we prune this entire branch of the search, as no path extending from `v` can 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`.

```java
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
                }
            }
        }
    }
}
```
### Algorithm
*   Build an adjacency list `adj` for the graph.
*   Use Dijkstra's algorithm starting from node 0 to precompute `minTimeToZero[i]`, the shortest time from every node `i` to node 0.
*   Initialize a global `max_quality = values[0]` (for the path just staying at 0).
*   Initialize a frequency array `visited_counts` of size `n`, with `visited_counts[0] = 1`.
*   Define a recursive function `dfs(u, time_left, visited_counts, current_quality)`.
*   In `dfs(u, time_left, ...)`:
    *   For each neighbor `v` of `u` with edge time `t`:
        *   If `time_left >= t`:
            *   **Pruning Step**: Check if `time_left - t >= minTimeToZero[v]`. If not, skip this path.
            *   If the check passes, update `visited_counts` and `new_quality`.
            *   If `v == 0`, update `max_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]`.
*   Start the search with `dfs(0, maxTime, visited_counts, values[0])`.
*   Return `max_quality`.

# Solutions
### Java

```java
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;
        }
      }
    }
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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

```