Maximum Weighted K-Edge Path - Video Solutions
3543. Maximum Weighted K-Edge Path | BiWeekly Contest 156
Maximum Weighted K-Edge Path - Video Solution
Watch 6 video solutions for Maximum Weighted K-Edge Path, a medium level problem involving Hash Table, Dynamic Programming, Graph. This walkthrough by Tech Courses has 638 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an integer n and a Directed Acyclic Graph (DAG) with n nodes labeled from 0 to n - 1. This is represented by a 2D array edges, where edges[i] = [ui, vi, wi] indicates a directed edge from node ui to vi with weight wi.
You are also given two integers, k and t.
Your task is to determine the maximum possible sum of edge weights for any path in the graph such that:
- The path contains exactly
kedges. - The total sum of edge weights in the path is strictly less than
t.
Return the maximum possible sum of weights for such a path. If no such path exists, return -1.
Example 1:
Input: n = 3, edges = [[0,1,1],[1,2,2]], k = 2, t = 4
Output: 3
Explanation:
- The only path with
k = 2edges is0 -> 1 -> 2with weight1 + 2 = 3 < t. - Thus, the maximum possible sum of weights less than
tis 3.
Example 2:
Input: n = 3, edges = [[0,1,2],[0,2,3]], k = 1, t = 3
Output: 2
Explanation:
- There are two paths with
k = 1edge:0 -> 1with weight2 < t.0 -> 2with weight3 = t, which is not strictly less thant.
- Thus, the maximum possible sum of weights less than
tis 2.
Example 3:
Input: n = 3, edges = [[0,1,6],[1,2,8]], k = 1, t = 6
Output: -1
Explanation:
- There are two paths with k = 1 edge:
0 -> 1with weight6 = t, which is not strictly less thant.1 -> 2with weight8 > t, which is not strictly less thant.
- Since there is no path with sum of weights strictly less than
t, the answer is -1.
Constraints:
1 <= n <= 3000 <= edges.length <= 300edges[i] = [ui, vi, wi]0 <= ui, vi < nui != vi1 <= wi <= 100 <= k <= 3001 <= t <= 600- The input graph is guaranteed to be a DAG.
- There are no duplicate edges.
Approach Overview
Problem Overview: You are given a weighted graph and an integer k. The task is to compute the maximum possible total weight of a path that uses exactly k edges. Nodes can appear multiple times unless restricted by the problem statement, so the focus is purely on maximizing weight while respecting the edge count constraint.
Approach 1: Brute Force DFS Enumeration (Exponential Time)
The most direct idea is to start a depth‑first search from every node and explore all paths of length k. At each step, recursively visit every outgoing edge while tracking the current weight and number of edges used. When the recursion depth reaches k, update the global maximum. This approach touches every possible path combination and quickly explodes in size as the branching factor grows. Time complexity is roughly O(V * d^k) where d is the average degree, and space complexity is O(k) for the recursion stack. It demonstrates the problem structure but is impractical for larger graphs.
Approach 2: Dynamic Programming on Edge Count (O(K * E))
A more scalable solution uses dynamic programming over the number of edges used. Define dp[i][v] as the maximum weight achievable when reaching node v using exactly i edges. Initialize the base case for zero edges, then iteratively build results for 1..k. For each iteration, scan every edge (u → v, w) and update dp[i][v] = max(dp[i][v], dp[i-1][u] + w). This resembles the relaxation step in Bellman‑Ford but limited to exactly k steps. The algorithm processes each edge for each edge-count layer, giving O(K * E) time and O(K * V) space.
To reduce memory, you can keep only two layers: the previous edge count and the current one. That drops space to O(V) while maintaining the same runtime. The graph itself is usually represented with adjacency lists from a graph structure, and intermediate values can be stored in arrays or a hash table if node IDs are sparse.
Recommended for interviews: The dynamic programming approach with edge-count transitions is what interviewers typically expect. Brute force DFS shows you understand the path enumeration aspect, but the DP formulation demonstrates algorithmic maturity. The key insight is recognizing that the number of edges used forms a natural DP dimension, allowing you to reuse results from k‑1 edges instead of recomputing paths repeatedly.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| DFS Path Enumeration | O(V * d^K) | O(K) | Small graphs or conceptual baseline to understand the search space |
| DP with Edge Count Table | O(K * E) | O(K * V) | General solution for weighted graphs when exact edge count is required |
| Space‑Optimized DP | O(K * E) | O(V) | Preferred in interviews or large graphs where memory usage matters |