2065. Maximum Path Quality of a Graph LeetCode Solution

In this guide, you will get 2065. Maximum Path Quality of a Graph LeetCode Solution with the best time and space complexity. The solution to Maximum Path Quality of a Graph problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Path Quality of a Graph solution in C++
Maximum Path Quality of a Graph solution in Java
Maximum Path Quality of a Graph solution in Python
Additional Resources

2065. Maximum Path Quality of a Graph LeetCode Solution image

Problem Statement of Maximum Path Quality of a Graph

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 3 -> 0. The total time taken is 10 + 10 = 20 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.

Complexity Analysis

Time Complexity: O(|V| + |E|), where |V| = |\texttt{values}| and |E| = |\texttt{edges}|
Space Complexity: O(|V| + |E|)

2065. Maximum Path Quality of a Graph LeetCode Solution in C++

class Solution {
 public:
  int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges,
                         int maxTime) {
    const int n = values.size();
    int ans = 0;
    vector<vector<pair<int, int>>> graph(n);
    vector<int> seen(n);
    seen[0] = 1;

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int time = edge[2];
      graph[u].emplace_back(v, time);
      graph[v].emplace_back(u, time);
    }

    dfs(graph, values, 0, values[0], maxTime, seen, ans);
    return ans;
  }

 private:
  void dfs(const vector<vector<pair<int, int>>>& graph,
           const vector<int>& values, int u, int quality, int remainingTime,
           vector<int>& seen, int& ans) {
    if (u == 0)
      ans = max(ans, quality);
    for (const auto& [v, time] : graph[u]) {
      if (time > remainingTime)
        continue;
      const int newQuality = quality + values[v] * (seen[v] == 0);
      ++seen[v];
      dfs(graph, values, v, newQuality, remainingTime - time, seen, ans);
      --seen[v];
    }
  }
};
/* code provided by PROGIEZ */

2065. Maximum Path Quality of a Graph LeetCode Solution in Java

class Solution {
  public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
    final int n = values.length;
    List<Pair<Integer, Integer>>[] graph = new List[n];
    int[] seen = new int[n];
    seen[0] = 1;

    for (int i = 0; i < n; ++i)
      graph[i] = new ArrayList<>();

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      final int time = edge[2];
      graph[u].add(new Pair<>(v, time));
      graph[v].add(new Pair<>(u, time));
    }

    dfs(graph, values, 0, values[0], maxTime, seen);
    return ans;
  }

  private int ans = 0;

  private void dfs(List<Pair<Integer, Integer>>[] graph, int[] values, int u, int quality,
                   int remainingTime, int[] seen) {
    if (u == 0)
      ans = Math.max(ans, quality);
    for (Pair<Integer, Integer> pair : graph[u]) {
      final int v = pair.getKey();
      final int time = pair.getValue();
      if (time > remainingTime)
        continue;
      final int newQuality = quality + values[v] * (seen[v] == 0 ? 1 : 0);
      ++seen[v];
      dfs(graph, values, v, newQuality, remainingTime - time, seen);
      --seen[v];
    }
  }
}
// code provided by PROGIEZ

2065. Maximum Path Quality of a Graph LeetCode Solution in Python

class Solution:
  def maximalPathQuality(
      self,
      values: list[int],
      edges: list[list[int]],
      maxTime: int,
  ) -> int:
    n = len(values)
    ans = 0
    graph = [[] for _ in range(n)]
    seen = [0] * n
    seen[0] = 1

    for u, v, time in edges:
      graph[u].append((v, time))
      graph[v].append((u, time))

    def dfs(u: int, quality: int, remainingTime: int):
      nonlocal ans
      if u == 0:
        ans = max(ans, quality)
      for v, time in graph[u]:
        if time > remainingTime:
          continue
        newQuality = quality + values[v] * (seen[v] == 0)
        seen[v] += 1
        dfs(v, newQuality, remainingTime - time)
        seen[v] -= 1

    dfs(0, values[0], maxTime)
    return ans
 # code by PROGIEZ