Maximum Path Quality of a Graph - Practice Coding Problems

Maximum Path Quality of a Graph - 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 i^th node. You are also given a 0-indexed 2D integer array edges, where each edges[j] = [u_j, v_j, time_j] indicates that there is an undirected edge between the nodes u_j and v_j, and it takes time_j 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.

Input & Output

Example 1 — Basic Round Trip

$ Input: values = [0,32,10,43], edges = [[0,1,10],[1,2,15],[0,3,10]], maxTime = 25

› Output: 75

💡 Note: Optimal path: 0 → 3 → 2 → 1 → 0. Time: 10+1+15+10=36 > 25, so try 0 → 1 → 0 → 3 → 0 (time=10+10+10=30 > 25). Better: 0 → 3 → 0 → 1 → 0 gives quality 0+43+32=75 in time 10+10+10=30 > 25. Actually: 0 → 1 → 0 gives 0+32=32 in time 20. Then 0 → 3 → 0 gives 0+43=43 in time 20. Best is 0 → 3 → 1 → 0 impossible due to no direct 3-1 edge. Correct path: 0 → 1 → 2 → 3 → 0 visiting nodes {0,1,2,3} = 0+32+10+43 = 85, but time = 10+15+1+10 = 36 > 25. Try 0 → 3 → 2 → 1 → 0: time 10+1+15+10=36 > 25. Try shorter: 0 → 1 → 0: time 20, quality 32. Limited to 25 time. Path 0 → 3 → 0: time 20, quality 43. Can do 0 → 3 → 2 → back? 0 → 3 (10) → 2 (1) total 11, quality 0+43+10=53, need 11 more to return. Can return via 2 → 1 → 0 (15+10=25, total 36 > 25). Try 2 → 3 → 0 (1+10=11, total 22 ≤ 25). So 0 → 3 → 2 → 3 → 0 visits {0,3,2}, quality = 85, time = 10+1+1+10 = 22 ≤ 25. Wait, that's wrong edge. Let me recalculate: 0 → 3 → 2 uses edge [3,2] but edges show [0,1,10],[1,2,15],[0,3,10]. Missing [3,2,1]. With all edges [[0,1,10],[1,2,15],[0,3,10],[3,2,1]], path 0 → 3 → 2 → 3 → 0 = 0+43+10+0 = 53 in time 10+1+1+10 = 22. But we can do better: 0 → 1 → 2 → 3 → 0 = 0+32+10+43 = 85 in time 10+15+1+10 = 36 > 25. So best within 25 is likely 0 → 3 → 2 → 3 → 0 = 53+0+10+43 = 53, no double counting: unique {0,3,2} = 0+43+10 = 53.

Example 2 — Just Stay at Start

$ Input: values = [5,10,15,20], edges = [[0,1,10],[1,2,10],[2,3,10]], maxTime = 5

› Output: 5

💡 Note: With only 5 time units, cannot visit any other node and return to 0 (each edge takes 10 time). Stay at node 0, quality = 5.

Example 3 — Quick Round Trip

$ Input: values = [1,2,3,4], edges = [[0,1,10],[1,2,10],[0,3,10]], maxTime = 30

› Output: 6

💡 Note: Can do 0 → 1 → 0 (quality = 1+2 = 3, time = 20) then 0 → 3 → 0 (adds +4, time +20 = 40 > 30). Or single trip 0 → 3 → 0 (quality = 1+4 = 5, time = 20). Or 0 → 1 → 0 → 3 → 0 would be time 40 > 30. Best single path: 0 → 1 → 0 = 3 (time 20), then can't do more. Wait, what about 0 → 1 → 2 → 1 → 0? Time = 10+10+10+10 = 40 > 30. Try 0 → 3 → 0 → 1 → 0? Time = 10+10+10+10 = 40 > 30. Actually, 0 → 1 → 0 → 3 → 0 impossible since we'd need 40 time but have 30. Best is either 0 → 1 → 0 (quality 3, time 20) or 0 → 3 → 0 (quality 5, time 20). Answer should be 5. But wait, we visit {0,3} so quality = values[0] + values[3] = 1 + 4 = 5. Hmm, let me reconsider the example. Maybe there's a better path I'm missing.

Constraints

n == values.length
1 ≤ n ≤ 1000
0 ≤ values[i] ≤ 10⁸
0 ≤ edges.length ≤ 2000
edges[j].length == 3
0 ≤ u_j < v_j ≤ n - 1
10 ≤ time_j, maxTime ≤ 100
There are at most four edges connected to each node.

Visualization

Tap to expand

Understanding the Visualization

Input Graph

Undirected graph with node values and edge times

Explore Paths

Try all round-trip paths within maxTime

Calculate Quality

Sum values of unique nodes visited

Key Takeaway

🎯 Key Insight: Use backtracking DFS with pruning to explore valid round-trip paths efficiently

Asked in

G Google 15 M Meta 12 a Amazon 8

The key insight is to use backtracking DFS to explore all possible round-trip paths while tracking unique visited nodes. The optimal approach uses path pruning to avoid impossible routes. Time: O(4^k), Space: O(n + maxTime) where k is the effective search depth after pruning.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force DFS	O(4^maxTime)	O(maxTime)	Try all possible paths from node 0 back to node 0 within time limit
Optimized Backtracking	O(4^k)	O(n + maxTime)	Use backtracking with pruning to avoid exploring impossible paths

Brute Force DFS — Algorithm Steps

Build adjacency list from edges
DFS from node 0 tracking current time and visited nodes
When back at node 0, update maximum quality
Backtrack to try all possibilities

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency list from edges

DFS Search

Recursively explore all paths from node 0

Track Quality

Sum values of unique visited nodes

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_NODES 1000

struct Edge {
    int to;
    int time;
    struct Edge* next;
};

struct Edge* graph[MAX_NODES];
int values[MAX_NODES];
bool visited[MAX_NODES];
int maxQuality;
int n;

void addEdge(int from, int to, int time) {
    struct Edge* edge = malloc(sizeof(struct Edge));
    edge->to = to;
    edge->time = time;
    edge->next = graph[from];
    graph[from] = edge;
}

void dfs(int node, int timeLeft, int currentQuality, int maxTime) {
    // If we're back at node 0 (and not the initial call), update max quality
    if (node == 0 && timeLeft < maxTime) {
        if (currentQuality > maxQuality) {
            maxQuality = currentQuality;
        }
    }
    
    // Try all neighbors
    struct Edge* edge = graph[node];
    while (edge) {
        int nextNode = edge->to;
        int travelTime = edge->time;
        
        if (timeLeft >= travelTime) {
            // Calculate new quality if visiting this neighbor
            int newQuality = currentQuality;
            if (!visited[nextNode]) {
                newQuality += values[nextNode];
            }
            
            // Visit neighbor
            visited[nextNode] = true;
            dfs(nextNode, timeLeft - travelTime, newQuality, maxTime);
            visited[nextNode] = false;
        }
        
        edge = edge->next;
    }
}

int solution(int* vals, int valsSize, int** edges, int edgesSize, int* edgesColSize, int maxTime) {
    n = valsSize;
    
    // Initialize graph and values
    for (int i = 0; i < n; i++) {
        graph[i] = NULL;
        values[i] = vals[i];
        visited[i] = false;
    }
    
    // Build adjacency list
    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]);
    }
    
    maxQuality = values[0];
    visited[0] = true;
    dfs(0, maxTime, values[0], maxTime);
    
    return maxQuality;
}

int main() {
    // Simplified input parsing
    int valsSize = 4;
    int vals[] = {0, 32, 10, 43};
    
    int edgesSize = 4;
    int edges_data[][3] = {{0,1,10},{1,2,15},{0,3,10},{3,2,1}};
    int* edges[4];
    for (int i = 0; i < 4; i++) {
        edges[i] = edges_data[i];
    }
    int edgesColSize[] = {3, 3, 3, 3};
    
    int maxTime = 25;
    
    int result = solution(vals, valsSize, edges, edgesSize, edgesColSize, maxTime);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(4^maxTime)

In worst case, we can make 4 choices at each step for maxTime steps

✓ Linear Growth

Space Complexity

O(maxTime)

Recursion depth limited by maxTime and visited set

✓ Linear Space

23.5K Views

Medium Frequency

~25 min Avg. Time

847 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force DFS — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler