Difficulty: 🟡 Medium
Topics: Hash Table, Dynamic Programming, Graph Theory

Solution

LeetCode 3543 - Maximum Weighted K-Edge Path

Problem Understanding

We are given a directed acyclic graph (DAG) with n nodes and weighted directed edges. Each edge is represented as [u, v, w], meaning there is a directed edge from node u to node v with weight w.

The goal is to find a path that satisfies two conditions:

The path contains exactly k edges.
The total weight of those edges is strictly less than t.

Among all such valid paths, we want the maximum possible total weight. If no valid path exists, we return -1.

A few details are important:

The graph is a DAG, so cycles do not exist.
Edge weights are positive integers between 1 and 10.
The threshold t is at most 600.
We need exactly k edges, not at most k.
The path may start at any node and end at any node.

The constraints reveal the most important observation:

n ≤ 300
edges.length ≤ 300
k ≤ 300
t ≤ 600

The threshold t is surprisingly small. This strongly suggests that tracking achievable weight sums may be more practical than tracking arbitrary path values.

Important edge cases include:

No path contains exactly k edges.
Some paths contain exactly k edges, but every weight sum is at least t.
k = 0, meaning the path consists of a single node and contributes weight 0.
The graph may contain disconnected components.
Multiple different paths may reach the same node with the same edge count but different weight sums.

Problem Understanding

The problem asks us to find a path in a directed acyclic graph (DAG) such that the path has exactly k edges and the sum of edge weights is strictly less than t. The DAG is represented as an integer n for the number of nodes and a list edges where each edge has a source u, destination v, and weight w. The output should be the maximum possible weight sum of any valid path, or -1 if no path meets the criteria.

The constraints tell us the graph is relatively small (n <= 300, edges.length <= 300), and the edge weights are small integers (1 <= wi <= 10). The DAG guarantee allows us to process nodes in topological order, which is a key insight for dynamic programming. Edge cases include situations where k is 0, no path is valid, or all path sums are greater than or equal to t.

In essence, we are solving a constrained path sum problem on a DAG, where the constraints are exact edge count and weight threshold. This is a classic setting for dynamic programming on graphs.

Approaches

Brute Force

A straightforward approach is to enumerate every path of exactly k edges.

Since the graph is a DAG, we could perform DFS from every node and generate all possible paths with length k. For each path, we compute its total weight and keep the largest sum that is strictly less than t.

This approach is correct because it explicitly examines every candidate path. However, it is far too slow. Even in a DAG, the number of paths can grow exponentially with the number of vertices.

Therefore, brute force is not practical for the given constraints.

Key Insight

The critical observation is that t ≤ 600.

Instead of remembering only the best path reaching a state, we can remember every achievable weight sum below t.

Define a dynamic programming state:

dp[node][steps] = set of achievable sums

More precisely:

We process paths by edge count.
For each node and each number of used edges, we store every achievable path weight less than t.

If we know a path reaches node u using e edges with sum s, then for every outgoing edge (u, v, w):

New edge count becomes e + 1
New sum becomes s + w

If s + w < t, then this new state is valid.

Since all stored sums are strictly less than t, and t ≤ 600, the number of distinct sums is bounded by 600. This keeps the state space manageable.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(k) recursion stack	Enumerates all paths of length `k`
Optimal	O(k × E × t)	O(n × t) per layer	DP over edge count and achievable sums

Algorithm Walkthrough

Optimal Dynamic Programming

Create a DP structure where current[node] stores all achievable weight sums for paths ending at node after a fixed number of edges.
Initialize the zero-edge state. A path with zero edges can start at any node and has total weight 0, so every node initially contains the sum {0}.
Repeat the transition process exactly k times.
For each directed edge (u, v, w), examine every achievable sum currently stored at node u.
Compute new_sum = sum + w.
If new_sum < t, insert it into the next layer for node v.
After processing all edges, replace the current layer with the newly generated layer.
After exactly k iterations, all stored sums correspond to paths containing exactly k edges.
Scan every node and every stored sum, and return the largest value found.
If no sums exist after the final iteration, return -1.

Why it works

The DP maintains the invariant that after processing e iterations, current[node] contains exactly the set of all weight sums less than t achievable by paths ending at node using exactly e edges.

The initialization correctly represents all zero-edge paths. Each transition extends every valid path by one edge while preserving the threshold condition. Since every valid path of length e + 1 must arise from some valid path of length e followed by one edge, the transition is complete and correct.

After k iterations, the DP contains exactly all valid paths with k edges, so taking the maximum stored sum yields the required answer. A brute-force approach would try every possible path of length k in the DAG, compute the sum of its weights, and track the maximum sum less than t. One could implement this recursively or via DFS with backtracking. While correct, this approach is infeasible because the number of paths grows exponentially with k and n. Specifically, the complexity would be O(n^k) in the worst case, which is far too slow for n and k up to 300.

Optimal Approach

The key observation is that the graph is a DAG. This allows us to use dynamic programming based on topological ordering. Define a DP table dp[node][edges] representing the maximum weight sum of a path ending at node with exactly edges edges. Initialize dp[node][0] = 0 for all nodes, since a path of 0 edges has weight 0. Then, iterate through nodes in topological order, and for each outgoing edge (u, v, w) update dp[v][e+1] = max(dp[v][e+1], dp[u][e] + w) for all valid e. Finally, after filling the DP table, scan all dp[node][k] entries to find the maximum sum less than t.

This approach is efficient because it leverages the DAG structure, avoids recomputation, and uses a fixed-size DP table.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^k)	O(k)	DFS all paths of length k; too slow
Optimal	O(n_k + edges_k)	O(n*k)	DP on topological order using exact k edges

Algorithm Walkthrough

Topological Sort: Compute a topological order of all nodes. This ensures that when we process a node u, all nodes with edges to u have already been processed. Topological sort can be done via Kahn's algorithm or DFS.
Initialize DP Table: Create a table dp[node][edges] where dp[i][j] stores the maximum sum of weights of a path ending at i with exactly j edges. Initialize all entries to -1 to indicate invalid paths. Set dp[node][0] = 0 for all nodes, since a 0-edge path has sum 0.
Process Nodes in Topological Order: For each node u in topological order, iterate through each outgoing edge (u, v, w). For each valid edge count e from 0 to k-1, if dp[u][e] != -1 (a path exists), update dp[v][e+1] = max(dp[v][e+1], dp[u][e] + w). This ensures the DP captures the maximum sum for exactly e+1 edges ending at v.
Compute Maximum Path: After processing all nodes, iterate over all nodes v and consider dp[v][k]. If dp[v][k] < t, it is a valid candidate. Track the maximum of all such candidates. If no valid paths exist, return -1.

Why it works: The DP table correctly captures the maximum sum for paths ending at each node with exactly j edges, and processing nodes in topological order ensures that all dependencies are resolved before updating a node. The invariant is that at any point, dp[node][edges] is the maximum sum of a path of length edges ending at node.

Python Solution

from typing import List

class Solution:
    def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int:
        current = [set() for _ in range(n)]

        for node in range(n):
            current[node].add(0)

        for _ in range(k):
            nxt = [set() for _ in range(n)]

            for u, v, w in edges:
                for total in current[u]:
                    new_total = total + w
                    if new_total < t:
                        nxt[v].add(new_total)

            current = nxt

        answer = -1

        for sums in current:
            if sums:
                answer = max(answer, max(sums))

        return answer

The implementation directly follows the dynamic programming formulation.

The variable current stores all achievable sums for the current edge count. Initially, every node contains the sum 0, representing a path of length zero.

Each iteration corresponds to adding one edge. We create a fresh layer nxt, then process every graph edge. For every achievable sum reaching the source vertex, we extend the path through the edge and store the resulting sum if it remains strictly below t.

After exactly k rounds, current contains only paths that use exactly k edges. We then scan all stored sums and return the maximum value. If no valid sum exists, the answer remains -1. from collections import defaultdict, deque

class Solution: def maxWeight(self, n: int, edges: List[List[int]], k: int, t: int) -> int: # Build graph adjacency list graph = defaultdict(list) indegree = [0] * n for u, v, w in edges: graph[u].append((v, w)) indegree[v] += 1

    # Topological sort using Kahn's algorithm
    topo_order = []
    queue = deque([i for i in range(n) if indegree[i] == 0])
    while queue:
        node = queue.popleft()
        topo_order.append(node)
        for nei, _ in graph[node]:
            indegree[nei] -= 1
            if indegree[nei] == 0:
                queue.append(nei)
    
    # DP table: dp[node][edges] = max weight sum of path ending at node with exact edges
    dp = [[-1] * (k + 1) for _ in range(n)]
    for i in range(n):
        dp[i][0] = 0  # path of 0 edges has weight 0
    
    # Fill DP table
    for u in topo_order:
        for v, w in graph[u]:
            for e in range(k):
                if dp[u][e] != -1:
                    dp[v][e + 1] = max(dp[v][e + 1], dp[u][e] + w)
    
    # Find maximum sum < t for paths with exactly k edges
    result = -1
    for i in range(n):
        if 0 <= dp[i][k] < t:
            result = max(result, dp[i][k])
    
    return result


**Explanation**: First, we construct a graph adjacency list and indegree array for topological sorting. After topological sort, we initialize the DP table with -1, except for 0-edge paths. We then iterate through nodes in topological order and update DP values for each outgoing edge. Finally, we scan the DP table to find the maximum sum for paths with exactly `k` edges that is strictly less than `t`.

## Go Solution

```go
func maxWeight(n int, edges [][]int, k int, t int) int {
	current := make([]map[int]struct{}, n)

	for i := 0; i < n; i++ {
		current[i] = map[int]struct{}{0: {}}
	}

	for step := 0; step < k; step++ {
		next := make([]map[int]struct{}, n)

		for i := 0; i < n; i++ {
			next[i] = make(map[int]struct{})
		}

		for _, edge := range edges {
			u, v, w := edge[0], edge[1], edge[2]

			for sum := range current[u] {
				newSum := sum + w
				if newSum < t {
					next[v][newSum] = struct{}{}
				}
			}
		}

		current = next
	}

	ans := -1

	for _, sums := range current {
		for sum := range sums {
			if sum > ans {
				ans = sum
			}
		}
	}

	return ans
}

The Go implementation mirrors the Python solution. Since Go does not have a built in set type, maps with empty struct values are used to represent sets of achievable sums. The empty struct consumes zero additional storage per entry and is the standard Go idiom for set representation.

All calculations fit comfortably within Go's int type because the largest possible sum below the threshold is less than 600.

Worked Examples

Example 1

Input:

n = 3
edges = [[0,1,1],[1,2,2]]
k = 2
t = 4

Initial state:

Node	Sums
0	{0}
1	{0}
2	{0}

After 1 edge:

Processing 0 -> 1 (1):

0 + 1 = 1

Processing 1 -> 2 (2):

0 + 2 = 2

Node	Sums
0	{}
1	{1}
2	{2}

After 2 edges:

Processing 0 -> 1 (1):

No sums at node 0

Processing 1 -> 2 (2):

1 + 2 = 3

Node	Sums
0	{}
1	{}
2	{3}

Maximum valid sum is 3.

Answer:

Example 2

Input:

n = 3
edges = [[0,1,2],[0,2,3]]
k = 1
t = 3

Initial state:

Node	Sums
0	{0}
1	{0}
2	{0}

After 1 edge:

Edge 0 -> 1:

0 + 2 = 2

Edge 0 -> 2:

0 + 3 = 3
Rejected because 3 is not strictly less than t

Final state:

Node	Sums
0	{}
1	{2}
2	{}

Maximum valid sum is 2.

Answer:

Example 3

Input:

n = 3
edges = [[0,1,6],[1,2,8]]
k = 1
t = 6

Initial state:

Node	Sums
0	{0}
1	{0}
2	{0}

After 1 edge:

Edge 0 -> 1:

0 + 6 = 6
Rejected

Edge 1 -> 2:

0 + 8 = 8
Rejected

Final state:

Node	Sums
0	{}
1	{}
2	{}

No valid sums exist.

Answer:

-1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k × E × t)	For each of `k` layers, every edge may process up to `t` achievable sums
Space	O(n × t)	Each node stores at most `t` distinct sums below the threshold

Since t ≤ 600 and E ≤ 300, the worst case remains manageable. The threshold bound is what makes this dynamic programming solution practical. Without the small value of t, storing all achievable sums would become too expensive.

Test Cases

from typing import List

s = Solution()

assert s.maxWeight(
    3,
    [[0, 1, 1], [1, 2, 2]],
    2,
    4
) == 3  # Example 1

assert s.maxWeight(
    3,
    [[0, 1, 2], [0, 2, 3]],
    1,
    3
) == 2  # Example 2

assert s.maxWeight(
    3,
    [[0, 1, 6], [1, 2, 8]],
    1,
    6
) == -1  # Example 3

assert s.maxWeight(
    1,
    [],
    0,
    1
) == 0  # Zero-edge path with weight 0

assert s.maxWeight(
    2,
    [],
    1,
    10
) == -1  # No edges available

assert s.maxWeight(
    4,
    [[0, 1, 2], [2, 3, 4]],
    2,
    10
) == -1  # No path of exactly two edges

assert s.maxWeight(
    3,
    [[0, 1, 2], [1, 2, 3]],
    2,
    5
) == -1  # Sum equals threshold, not allowed

assert s.maxWeight(
    3,
    [[0, 1, 2], [1, 2, 3]],
    2,
    6
) == 5  # Sum strictly below threshold

assert s.maxWeight(
    4,
    [[0, 1, 1], [0, 2, 2], [1, 3, 4], [2, 3, 3]],
    2,
    10
) == 6  # Multiple paths, choose largest valid sum

assert s.maxWeight(
    4,
    [[0, 1, 5], [0, 2, 5], [1, 3, 5], [2, 3, 5]],
    2,
    11
) == 10  # Duplicate achievable sums

Test Summary

Test	Why
Example 1	Basic valid path
Example 2	Threshold equality rejection
Example 3	No valid path
Single node, k=0	Valid zero-edge path
Empty graph, k>0	No path exists
Disconnected graph	Exact edge count impossible
Sum equals t	Strict inequality validation
Sum below t	Valid threshold handling
Multiple candidate paths	Choose maximum valid sum
Duplicate sums	Set deduplication correctness

Edge Cases

Zero Edge Paths

When k = 0, a valid path consists of a single node and no edges. The weight sum is therefore 0. A common mistake is to assume every path must traverse at least one edge. The implementation initializes every node with sum 0, which naturally handles the zero-edge case. If t > 0, the answer becomes 0.

Paths Reaching the Threshold Exactly

The problem requires the total weight to be strictly less than t. It is easy to accidentally use <= t during transitions. The implementation explicitly checks new_total < t, ensuring that sums equal to the threshold are rejected.

No Path with Exactly k Edges

A graph may contain paths, but none with exactly k edges. For example, a graph might contain only isolated edges while k = 5. After repeatedly applying transitions, all DP sets become empty. The final scan finds no valid sums and correctly returns -1.

Multiple Ways to Reach the Same State

Different paths may end at the same node with the same weight sum and edge count. Storing sums in a set automatically removes duplicates. This prevents unnecessary repeated work while preserving all distinct achievable totals needed for future transitions.

Disconnected Components

The graph may contain several disconnected DAG components. Since every node is initialized as a potential starting node, the algorithm automatically considers paths originating from any component without requiring special handling. graph := make([][][2]int, n) indegree := make([]int, n) for _, edge := range edges { u, v, w := edge[0], edge[1], edge[2] graph[u] = append(graph[u], [2]int{v, w}) indegree[v]++ }

// Topological sort
topoOrder := make([]int, 0, n)
queue := make([]int, 0)
for i := 0; i < n; i++ {
    if indegree[i] == 0 {
        queue = append(queue, i)
    }
}
for len(queue) > 0 {
    node := queue[0]
    queue = queue[1:]
    topoOrder = append(topoOrder, node)
    for _, edge := range graph[node] {
        v := edge[0]
        indegree[v]--
        if indegree[v] == 0 {
            queue = append(queue, v)
        }
    }
}

// DP table
dp := make([][]int, n)
for i := 0; i < n; i++ {
    dp[i] = make([]int, k+1)
    for j := range dp[i] {
        dp[i][j] = -1
    }
    dp[i][0] = 0
}

// Fill DP table
for _, u := range topoOrder {
    for _, edge := range graph[u] {
        v, w := edge[0], edge[1]
        for e := 0; e < k; e++ {
            if dp[u][e] != -1 {
                candidate := dp[u][e] + w
                if candidate > dp[v][e+1] {
                    dp[v][e+1] = candidate
                }
            }
        }
    }
}

// Find maximum valid path
result := -1
for i := 0; i < n; i++ {
    if dp[i][k] >= 0 && dp[i][k] < t {
        if dp[i][k] > result {
            result = dp[i][k]
        }
    }
}
return result

}


**Go-specific notes**: We use slices instead of Python lists and arrays, initialize the DP table with