Skip to main content
Talentd

Maximum Weighted K-Edge Path - Solution & Explanation

MediumHash TableDynamic ProgrammingGraph4 min read
Practice this problem

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 k edges.
  • 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 = 2 edges is 0 -> 1 -> 2 with weight 1 + 2 = 3 < t.
  • Thus, the maximum possible sum of weights less than t is 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 = 1 edge:
    • 0 -> 1 with weight 2 < t.
    • 0 -> 2 with weight 3 = t, which is not strictly less than t.
  • Thus, the maximum possible sum of weights less than t is 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 -> 1 with weight 6 = t, which is not strictly less than t.
    • 1 -> 2 with weight 8 > t, which is not strictly less than t.
  • Since there is no path with sum of weights strictly less than t, the answer is -1.

 

Constraints:

  • 1 <= n <= 300
  • 0 <= edges.length <= 300
  • edges[i] = [ui, vi, wi]
  • 0 <= ui, vi < n
  • ui != vi
  • 1 <= wi <= 10
  • 0 <= k <= 300
  • 1 <= 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.

Solutions for this problem are being prepared.

Try solving it yourself

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
DFS Path EnumerationO(V * d^K)O(K)Small graphs or conceptual baseline to understand the search space
DP with Edge Count TableO(K * E)O(K * V)General solution for weighted graphs when exact edge count is required
Space‑Optimized DPO(K * E)O(V)Preferred in interviews or large graphs where memory usage matters

Video Solution

3543. Maximum Weighted K-Edge Path | BiWeekly Contest 156 • Tech Courses • 638 views views

Watch 5 more video solutions →

Frequently Asked Questions

Is Maximum Weighted K-Edge Path easy or hard?
Maximum Weighted K-Edge Path is generally considered a medium-level problem. The difficulty comes from recognizing the dynamic programming state based on the number of edges and applying graph edge relaxation efficiently.
Maximum Weighted K-Edge Path Python/Java solution
Implement the DP transition using arrays or lists to track the best value for each node after every edge count. Iterate K times and relax all edges during each iteration. The same logic translates directly across Python, Java, C++, and Go implementations.
How to solve Maximum Weighted K-Edge Path in O(K·E)?
Build a DP table where each layer represents paths that use exactly i edges. For every iteration i, iterate through all edges (u → v, w) and update dp[i][v] = max(dp[i][v], dp[i−1][u] + w). This edge-relaxation process repeated K times guarantees the maximum weight path with exactly K edges.
What is the best approach for Maximum Weighted K-Edge Path?
The best approach uses dynamic programming over the number of edges. Define dp[i][v] as the maximum weight achievable at node v using exactly i edges, and relax every edge for each step from 1 to K. This processes each edge K times, giving O(K·E) time complexity and O(V) space with optimization.
Is Maximum Weighted K-Edge Path asked at Google/Amazon/Meta?
Graph dynamic programming problems that constrain path length appear frequently in interviews at companies like Google, Amazon, and Meta. Variants such as K-step shortest paths or K-edge constrained paths test understanding of graph DP and Bellman-Ford style transitions.
What data structure is used in Maximum Weighted K-Edge Path?
The solution relies on graph representations such as adjacency lists along with dynamic programming arrays. Hash tables may be used when node identifiers are sparse or when storing intermediate states for nodes dynamically.
What is the time complexity of Maximum Weighted K-Edge Path?
The optimal dynamic programming solution runs in O(K·E) time, where K is the required number of edges and E is the number of edges in the graph. Space complexity can be O(K·V) with a full DP table or reduced to O(V) using two rolling arrays.

Ready to solve this problem?

Practice Maximum Weighted K-Edge Path with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Longest Substring Without Repeating Characters