Talentd
For employersSign in
JobsInternshipsPracticeResume toolsCompaniesArticles
For employers
FleetCode
Make and follow sheets.Sign in

Maximum Path Quality of a Graph solution and explanation

HardArrayBacktrackingGraph8 min read63.1% acceptanceUpdated 9 Apr 2026
Asked atSAPAppleSalesforceDoorDashGoogle
Practise Maximum Path Quality of a Graph
14:20
2065. Maximum Path Quality of a Graph | Leetcode Weekly contest 266 | Graph | DFS | DSA | CPTejpratap Pandey · 14:20 · 2K viewsWatch on YouTube
6 more videos on this problem
  1. 2065. Maximum Path Quality of a Graph | Leetcode Weekly contest 266 | Graph | DFS | DSA | CPTejpratap Pandey · 14:20 · 2K views
  2. 2065. Maximum Path Quality of a Graph (Leetcode Hard)Programming Live with Larry · 34:55 · 1K views
  3. 【每日一题】LeetCode 2065. Maximum Path Quality of a GraphHuifeng Guan · 21:48 · 1K views
  4. Leetcode 2065. Maximum Path Quality of a Graph [Solution]Elite Code · 21:25 · 730 views
  5. #LC-2065#Maximum Path Quality of a Graph#DECODE DSA # LEVEL UP#MISCELLANEOUS #leetcode#challengeDecode · 7:34 · 253 views
  6. 2065. Maximum Path Quality of a Graph | Leetcode Hard | DFS | Graph ProblemsAniket Wattamwar · 16:42 · 166 views
  7. LeetCode 2065: Maximum Path Quality of a GraphAlitaCode · 30:50 · 11 views

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. 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 <= 49.
The nodes visited are 0, 1, and 3, giving a maximal path quality of 0 + 32 + 43 = 75.

Example 2:

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:

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.

Approach overview

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.

Approach 1: DFS with Backtracking

This approach involves using Depth-First Search (DFS) to explore all possible paths starting and ending at node 0. We keep track of the current time and quality of each path. By using a set, we ensure each unique node's value is added only once. Backtracking allows us to explore different paths efficiently.

from collections import defaultdict

class Solution:
    def maximalPathQuality(self, values, edges, maxTime):
        graph = defaultdict(list)
        for u, v, time in edges:
            graph[u].append((v, time))
            graph[v].append((u, time))
        
        self.maxQuality = values[0]
        
        def dfs(node, timeLeft, currentQuality, visited):
            if timeLeft < 0:
                return
            self.maxQuality = max(self.maxQuality, currentQuality)
            for neighbor, travelTime in graph[node]:
                isNewNode = neighbor not in visited
                if isNewNode:
                    visited.add(neighbor)
                dfs(neighbor, timeLeft - travelTime, currentQuality + (values[neighbor] if isNewNode else 0), visited)
                if isNewNode:
                    visited.remove(neighbor)

        visited = set([0])
        dfs(0, maxTime, values[0], visited)
        return self.maxQuality

# Usage
solution = Solution()
values = [0, 32, 10, 43]
edges = [[0, 1, 10], [1, 2, 15], [0, 3, 10]]
maxTime = 49
print("Maximum Path Quality:", solution.maximalPathQuality(values, edges, maxTime))
import java.util.*;

class Graph {
    List<int[]>[] adj;
    int maxQuality;

    void dfs(int[] values, Set<Integer> visited, int node, int quality, int timeLeft) {
        if (timeLeft < 0) return;
        maxQuality = Math.max(maxQuality, quality);
        for (int[] edge : adj[node]) {
            int neighbor = edge[0], timeCost = edge[1];
            boolean isNewVisit = visited.add(neighbor);
            dfs(values, visited, neighbor, quality + (isNewVisit ? values[neighbor] : 0), timeLeft - timeCost);
            if (isNewVisit) visited.remove(neighbor);
        }
    }
}

public class Solution {
    public int maximalPathQuality(int[] values, int[][] edges, int maxTime) {
        Graph graph = new Graph();
        graph.adj = new ArrayList[values.length];
        for (int i = 0; i < values.length; i++) graph.adj[i] = new ArrayList<>();
        for (int[] edge : edges) {
            graph.adj[edge[0]].add(new int[]{edge[1], edge[2]});
            graph.adj[edge[1]].add(new int[]{edge[0], edge[2]});
        }
        graph.maxQuality = values[0];
        Set<Integer> visited = new HashSet<>();
        visited.add(0);
        graph.dfs(values, visited, 0, values[0], maxTime);
        return graph.maxQuality;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        int[] values = {0, 32, 10, 43};
        int[][] edges = {{0, 1, 10}, {1, 2, 15}, {0, 3, 10}};
        int maxTime = 49;
        System.out.println("Maximum Path Quality: " + sol.maximalPathQuality(values, edges, maxTime));
    }
}
#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;

vector<pair<int, int>> adj[1000];
int maxQuality;

void dfs(vector<int>& values, unordered_set<int>& visited, int node, int currentQuality, int leftoverTime) {
    if (leftoverTime < 0) return;
    maxQuality = max(maxQuality, currentQuality);
    for (auto& [neighbor, time] : adj[node]) {
        bool firstVisit = visited.find(neighbor) == visited.end();
        if (firstVisit) visited.insert(neighbor);
        dfs(values, visited, neighbor, currentQuality + (firstVisit ? values[neighbor] : 0), leftoverTime - time);
        if (firstVisit) visited.erase(neighbor);
    }
}

int maximalPathQuality(vector<int>& values, vector<vector<int>>& edges, int maxTime) {
    for (auto &edge : edges) {
        adj[edge[0]].emplace_back(edge[1], edge[2]);
        adj[edge[1]].emplace_back(edge[0], edge[2]);
    }
    unordered_set<int> visited = {0};
    maxQuality = values[0];
    dfs(values, visited, 0, values[0], maxTime);
    return maxQuality;
}

int main() {
    vector<int> values = {0, 32, 10, 43};
    vector<vector<int>> edges = {{0, 1, 10}, {1, 2, 15}, {0, 3, 10}};
    int maxTime = 49;
    cout << "Maximum Path Quality: " << maximalPathQuality(values, edges, maxTime) << endl;
    return 0;
}
var maximalPathQuality = function(values, edges, maxTime) {
    const graph = {};
    for (let [u, v, time] of edges) {
        if (!graph[u]) graph[u] = [];
        if (!graph[v]) graph[v] = [];
        graph[u].push([v, time]);
        graph[v].push([u, time]);
    }
    let maxQuality = values[0];
    
    function dfs(node, timeLeft, currentQuality, visited) {
        if (timeLeft < 0) return;
        maxQuality = Math.max(maxQuality, currentQuality);
        if (!graph[node]) return;
        for (let [neighbor, travelTime] of graph[node]) {
            const isFirstVisit = !visited.has(neighbor);
            if (isFirstVisit) visited.add(neighbor);
            dfs(neighbor, timeLeft - travelTime, currentQuality + (isFirstVisit ? values[neighbor] : 0), visited);
            if (isFirstVisit) visited.delete(neighbor);
        }
    }
    const visited = new Set([0]);
    dfs(0, maxTime, values[0], visited);
    return maxQuality;
};

// Usage
let values = [0, 32, 10, 43];
let edges = [[0, 1, 10], [1, 2, 15], [0, 3, 10]];
let maxTime = 49;
console.log("Maximum Path Quality:", maximalPathQuality(values, edges, maxTime));
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_N 1000

typedef struct {
    int node, time;
} Edge;

Edge* graph[MAX_N];
int sizes[MAX_N];
int maxQuality;
int visited[MAX_N];

void addEdge(int u, int v, int time) {
    graph[u] = realloc(graph[u], sizeof(Edge)*(sizes[u]+1));
    graph[u][sizes[u]].node = v;
    graph[u][sizes[u]].time = time;
    sizes[u]++;
}

void dfs(int* values, int currentNode, int timeLeft, int currentQuality) {
    if (timeLeft < 0) return;
    maxQuality = maxQuality > currentQuality ? maxQuality : currentQuality;
    for (int i = 0; i < sizes[currentNode]; i++) {
        int nextNode = graph[currentNode][i].node;
        int travelTime = graph[currentNode][i].time;
        int newQuality = visited[nextNode] == 0 ? currentQuality + values[nextNode] : currentQuality;
        visited[nextNode]++;
        dfs(values, nextNode, timeLeft - travelTime, newQuality);
        visited[nextNode]--;
    }
}

int maximalPathQuality(int* values, int valuesSize, int** edges, int edgesSize, int* edgesColSize, int maxTime) {
    memset(sizes, 0, sizeof(sizes));
    memset(visited, 0, sizeof(visited));
    for (int i = 0; i < MAX_N; i++) {
        graph[i] = NULL;
    }
    for (int i = 0; i < edgesSize; i++) {
        addEdge(edges[i][0], edges[i][1], edges[i][2]);
        addEdge(edges[i][1], edges[i][0], edges[i][2]);
    }
    visited[0] = 1;
    maxQuality = values[0];
    dfs(values, 0, maxTime, values[0]);
    for (int i = 0; i < MAX_N; i++) {
        free(graph[i]);
    }
    return maxQuality;
}
using System;
using System.Collections.Generic;

class Solution {
    int maxQuality;

    public int MaximalPathQuality(int[] values, int[][] edges, int maxTime) {
        var graph = new List<Tuple<int, int>>[values.Length];
        for (int i = 0; i < values.Length; i++) graph[i] = new List<Tuple<int, int>>();
        foreach (var edge in edges) {
            graph[edge[0]].Add(Tuple.Create(edge[1], edge[2]));
            graph[edge[1]].Add(Tuple.Create(edge[0], edge[2]));
        }
        maxQuality = values[0];
        var visited = new HashSet<int> { 0 };
        Dfs(values, graph, 0, maxTime, values[0], visited);
        return maxQuality;
    }

    private void Dfs(int[] values, List<Tuple<int, int>>[] graph, int node, int timeLeft, int currentQuality, HashSet<int> visited) {
        if (timeLeft < 0) return;
        maxQuality = Math.Max(maxQuality, currentQuality);
        foreach (var (neighbor, travelTime) in graph[node]) {
            bool isFirstVisit = visited.Add(neighbor);
            Dfs(values, graph, neighbor, timeLeft - travelTime, currentQuality + (isFirstVisit ? values[neighbor] : 0), visited);
            if (isFirstVisit) visited.Remove(neighbor);
        }
    }

    public static void Main() {
        var solution = new Solution();
        int[] values = { 0, 32, 10, 43 };
        int[][] edges = { new int[] { 0, 1, 10 }, new int[] { 1, 2, 15 }, new int[] { 0, 3, 10 } };
        int maxTime = 49;
        Console.WriteLine("Maximum Path Quality: " + solution.MaximalPathQuality(values, edges, maxTime));
    }
}

This Python method employs DFS recursion and a defaultdict to form the adjacency list. A DFS is initialized from node 0 with backtracking using a set for unique nodes and updated path quality, respecting the max time constraint.

Complexity

Time Complexity: O((E * T)^2), where E represents edges and T is maxTime.
Space Complexity: O(N + E), considering adjacency list and visited node set.

Try this approach in the editor

Approach 2: DFS

We observe the data range of the problem and find that the number of edges in each valid path starting from 0 does not exceed \frac{maxTime}{min(time_j)} = \frac{100}{10} = 10, and each node has at most four edges. Therefore, we can directly use naive DFS to brute-force search all valid paths.

First, we store the edges of the graph in the adjacency list g. Then, we design a function dfs(u, cost, value), where u represents the current node number, and cost and value respectively represent the cost time and value of the current path. Additionally, we use an array vis of length n to record whether each node has been visited. Initially, we mark node 0 as visited.

The logic of the function dfs(u, cost, value) is as follows:

  • If the current node number u equals 0, it means we have returned to the starting point, so we update the answer to max(ans, value);
  • For each neighbor node v of the current node u, if the current path's cost time plus the time t of the edge (u, v) does not exceed maxTime, then we can choose to continue visiting node v;
    • If node v has already been visited, we directly recursively call dfs(v, cost + t, value);
    • If node v has not been visited, we mark node v as visited, then recursively call dfs(v, cost + t, value + values[v]), and finally restore the visit status of node v.

In the main function, we call dfs(0, 0, values[0]) and return the answer ans.

The time complexity is O(n + m + 4^{\frac{maxTime}{min(time_j)}}), and the space complexity is O(n + m + \frac{maxTime}{min(time_j)}). Here, n and m respectively represent the number of nodes and edges.

function maximalPathQuality(values: number[], edges: number[][], maxTime: number): number {
    const n = values.length;
    const g: [number, number][][] = Array.from({ length: n }, () => []);
    for (const [u, v, t] of edges) {
        g[u].push([v, t]);
        g[v].push([u, t]);
    }
    const vis: boolean[] = Array(n).fill(false);
    vis[0] = true;
    let ans = 0;
    const dfs = (u: number, cost: number, value: number) => {
        if (u === 0) {
            ans = Math.max(ans, value);
        }
        for (const [v, t] of 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;
                }
            }
        }
    };
    dfs(0, 0, values[0]);
    return ans;
}
func maximalPathQuality(values []int, edges [][]int, maxTime int) (ans int) {
	n := len(values)
	g := make([][][2]int, n)
	for _, e := range edges {
		u, v, t := e[0], e[1], e[2]
		g[u] = append(g[u], [2]int{v, t})
		g[v] = append(g[v], [2]int{u, t})
	}
	vis := make([]bool, n)
	vis[0] = true
	var dfs func(u, cost, value int)
	dfs = func(u, cost, value int) {
		if u == 0 {
			ans = max(ans, value)
		}
		for _, e := range g[u] {
			v, t := e[0], 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
				}
			}
		}
	}
	dfs(0, 0, values[0])
	return
}
Try this approach in the editor

Complexity comparison

ApproachComplexity
DFS with Backtracking

Time Complexity: O((E * T)^2), where E represents edges and T is maxTime.
Space Complexity: O(N + E), considering adjacency list and visited node set.

DFS–

Complexity analysis

ApproachTimeSpaceWhen to Use
Brute Force DFS Path EnumerationExponential in number of valid pathsO(V)Understanding the problem or verifying correctness on small graphs
DFS with Backtracking and Visit CountingExponential (bounded by maxTime and branching factor)O(V)Recommended solution for interviews and competitive programming

Frequently asked questions

Is Maximum Path Quality of a Graph easy or hard?

Maximum Path Quality of a Graph is classified as Hard. The difficulty comes from exploring many graph paths while handling node revisits, time constraints, and ensuring node values are counted only once using backtracking.

Maximum Path Quality of a Graph Python/Java solution

The typical implementation builds an adjacency list, then runs DFS from node 0 while tracking remaining time and visit counts. When a node is visited for the first time its value is added to the current score. Implementations in Python, Java, C++, C#, and JavaScript follow the same DFS backtracking pattern.

How to solve Maximum Path Quality of a Graph in O(n)?

An O(n) solution is not feasible because the problem requires evaluating many possible paths with different revisit patterns. The best practical approach is DFS with backtracking that explores all valid paths constrained by maxTime while counting node values only once per path.

What is the best approach for Maximum Path Quality of a Graph?

DFS with backtracking is the most effective approach. Build an adjacency list for the graph, track how many times each node is visited, and only add a node's value the first time it appears in the path. Explore neighbors while the remaining time is non‑negative and update the result whenever the traversal returns to node 0.

Is Maximum Path Quality of a Graph asked at Google/Amazon/Meta?

Graph traversal and backtracking problems similar to Maximum Path Quality of a Graph frequently appear in interviews at companies like Google, Amazon, and Meta. The question tests graph modeling, recursion, and careful state restoration during DFS.

What data structure is used in Maximum Path Quality of a Graph?

The core data structure is an adjacency list to represent the graph. A visit counter array tracks how many times each node is visited so node values are only added once. Recursion or an explicit stack is used to perform depth‑first search with backtracking.

What is the time complexity of Maximum Path Quality of a Graph?

The DFS backtracking solution runs in exponential time because it may explore many possible paths within the maxTime constraint. However, the maximum depth of recursion is limited by travel time and edge weights. Space complexity is O(V) for the recursion stack and visit tracking array.

Comments

Next problem · similarCherry PickupHard
Now write it yourselfClose this page and solve Maximum Path Quality of a Graph in the editor, without looking.
Practise Maximum Path Quality of a Graph