Maximum Path Quality of a Graph — LeetCode 2065 Python Solution
HardGraphArrayBacktracking
- Problem
- #2065
- Pattern
- Backtracking
- Reading time
- 5 min
- Source
- leetcode.com
The 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.
Example
- 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.
Python solution
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 ansComplexity
| Measure | Complexity |
|---|---|
| Time | O(n + m + 4^{\frac{\textit{maxTime}}{\min(time_j)}}) |
| Space | O(n + m + \frac{\textit{maxTime}}{\min(time_j)}) auxiliary |
Pattern: Backtracking
Build candidates one choice at a time and abandon a branch the moment it cannot work. LeetCode 2065. Maximum Path Quality of a Graph is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Backtracking.
The backtracking guide has the Python template for the pattern and the 105 LeetCode problems that use it.
Related problems
Frequently asked questions
- How hard is LeetCode 2065. Maximum Path Quality of a Graph?
- LeetCode 2065. Maximum Path Quality of a Graph is rated Hard on LeetCode.
- What is the time complexity of LeetCode 2065. Maximum Path Quality of a Graph?
- The Python solution on this page runs in O(n + m + 4^{\frac{\textit{maxTime}}{\min(time_j)}}).
- What is the space complexity of LeetCode 2065. Maximum Path Quality of a Graph?
- The Python solution on this page uses O(n + m + \frac{\textit{maxTime}}{\min(time_j)}) auxiliary space.
- What topics does LeetCode 2065. Maximum Path Quality of a Graph cover?
- LeetCode 2065. Maximum Path Quality of a Graph is tagged Graph, Array and Backtracking on LeetCode.