3543. Maximum Weighted K-Edge Path LeetCode Solution

3 months ago

LeetCode Admin

5 minutes

In this guide, you will get 3543. Maximum Weighted K-Edge Path LeetCode Solution with the best time and space complexity. The solution to Maximum Weighted K-Edge Path problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Maximum Weighted K-Edge Path solution in C++
Maximum Weighted K-Edge Path solution in Java
Maximum Weighted K-Edge Path solution in Python
Additional Resources

3543. Maximum Weighted K-Edge Path LeetCode Solution image

Problem Statement of Maximum Weighted K-Edge Path

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 1 with weight 2 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.

Complexity Analysis

Time Complexity: O(n^3k)
Space Complexity: O(n^2k)

3543. Maximum Weighted K-Edge Path LeetCode Solution in C++

class Solution {
 public:
  int maxWeight(int n, vector<vector<int>>& edges, int k, int t) {
    vector<vector<pair<int, int>>> graph(n);
    // dp[u][i] := the set of possible path sums ending at node u with i edges
    vector<unordered_map<int, unordered_set<int>>> dp(n);

    for (const vector<int>& edge : edges) {
      const int u = edge[0];
      const int v = edge[1];
      const int w = edge[2];
      graph[u].emplace_back(v, w);
    }

    for (int u = 0; u < n; ++u)
      dp[u][0].insert(0);  // zero edges = sum 0

    for (int i = 0; i < k; ++i)
      for (int u = 0; u < n; ++u)
        if (dp[u].contains(i))
          for (const int currSum : dp[u][i])
            for (const auto& [v, w] : graph[u]) {
              const int newSum = currSum + w;
              if (newSum < t)
                dp[v][i + 1].insert(newSum);
            }

    int ans = -1;

    for (int u = 0; u < n; ++u)
      if (dp[u].contains(k))
        for (const int sum : dp[u][k])
          ans = max(ans, sum);

    return ans;
  }
};
/* code provided by PROGIEZ */

3543. Maximum Weighted K-Edge Path LeetCode Solution in Java

class Solution {
  public int maxWeight(int n, int[][] edges, int k, int t) {
    List<Pair<Integer, Integer>>[] graph = new List[n];
    // dp[i][j] := the set of possible path sums ending at node i with j edges
    Map<Integer, Set<Integer>>[] dp = new Map[n];

    for (int u = 0; u < n; ++u) {
      graph[u] = new ArrayList<>();
      dp[u] = new HashMap<>();
    }

    for (int[] edge : edges) {
      final int u = edge[0];
      final int v = edge[1];
      final int w = edge[2];
      graph[u].add(new Pair<>(v, w));
    }

    for (int u = 0; u < n; ++u) {
      dp[u].putIfAbsent(0, new HashSet<>());
      dp[u].get(0).add(0); // zero edges = sum 0
    }

    for (int i = 0; i < k; ++i)
      for (int u = 0; u < n; ++u)
        if (dp[u].containsKey(i))
          for (final int currSum : dp[u].get(i))
            for (Pair<Integer, Integer> pair : graph[u]) {
              final int v = pair.getKey();
              final int w = pair.getValue();
              final int newSum = currSum + w;
              if (newSum < t) {
                dp[v].putIfAbsent(i + 1, new HashSet<>());
                dp[v].get(i + 1).add(newSum);
              }
            }

    int ans = -1;

    for (int u = 0; u < n; ++u)
      if (dp[u].containsKey(k))
        for (final int sum : dp[u].get(k))
          ans = Math.max(ans, sum);

    return ans;
  }
}
// code provided by PROGIEZ

3543. Maximum Weighted K-Edge Path LeetCode Solution in Python

class Solution:
  def maxWeight(self, n: int, edges: list[list[int]], k: int, t: int) -> int:
    graph = [[] for _ in range(n)]
    # dp[u][i] := the set of possible path sums ending at node u with i edges
    dp = [defaultdict(set) for _ in range(n)]

    for u, v, w in edges:
      graph[u].append((v, w))

    for u in range(n):
      dp[u][0].add(0)  # zero edges = sum 0

    for i in range(k):
      for u in range(n):
        for currSum in dp[u][i]:
          for v, w in graph[u]:
            newSum = currSum + w
            if newSum < t:
              dp[v][i + 1].add(newSum)

    ans = -1

    for u in range(n):
      if k in dp[u]:
        ans = max(ans, max(dp[u][k]))

    return ans
 # code by PROGIEZ