How do you solve Modify Graph Edge Weights on LeetCode?

Modify Graph Edge Weights (LeetCode #2699) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: The shortest path must be calculated first to understand how much adjustment is needed.

What is the time complexity of Modify Graph Edge Weights?

The optimal solution for Modify Graph Edge Weights runs in O(n log n) time and uses O(n) space. The optimal solution runs in O(n log n) due to Dijkstra's algorithm, which is efficient for finding the shortest path in graphs.

What is the brute force solution for Modify Graph Edge Weights?

The brute force approach for Modify Graph Edge Weights is Brute Force, with O(n²) time complexity and O(1) space complexity. We can try all possible combinations of positive weights for the edges with -1 and check if any combination results in the desired shortest path. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n log n).

What algorithm or data structure is used to solve Modify Graph Edge Weights?

Modify Graph Edge Weights uses the following concepts: Graph Theory, Heap (Priority Queue), Shortest Path. The recommended patterns to study are: Graph Traversal (Dijkstra's Algorithm), Greedy Algorithms (distributing weights).

What are the interview tips for Modify Graph Edge Weights?

Always clarify the problem requirements and constraints with the interviewer. Think about edge cases, such as when there are no negative weights or when the target is unreachable. Practice explaining your thought process while coding, as communication is key in interviews.

What are common mistakes when solving Modify Graph Edge Weights?

Failing to check if the shortest path is already greater than or equal to the target before modifying weights. Not considering how to distribute the required weight across multiple negative edges.

#2699

Modify Graph Edge Weights

Hard

Graph TheoryHeap (Priority Queue)Shortest PathGraph Traversal (Dijkstra's Algorithm)Greedy Algorithms (distributing weights)

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

Instead of brute-forcing all combinations, we can use a more strategic approach. First, we calculate the shortest path using only positive weights, then determine how much we need to adjust the negative weights to reach the target.

⚙️

Algorithm

4 steps

1Step 1: Build the graph and calculate the shortest path from source to destination using Dijkstra's algorithm, considering only edges with positive weights.
2Step 2: If the shortest path is already greater than or equal to the target, return an empty array as it's impossible.
3Step 3: Calculate the difference needed to reach the target from the current shortest path.
4Step 4: Distribute this difference among the edges with -1, assigning weights such that the total equals the difference.

solution.py40 lines

1def modifyGraph(n, edges, source, destination, target):
2    import heapq
3
4    def dijkstra(start, graph):
5        dist = {i: float('inf') for i in range(n)}
6        dist[start] = 0
7        pq = [(0, start)]
8        while pq:
9            d, node = heapq.heappop(pq)
10            if d > dist[node]: continue
11            for neighbor, weight in graph[node]:
12                if weight > 0:
13                    if dist[node] + weight < dist[neighbor]:
14                        dist[neighbor] = dist[node] + weight
15                        heapq.heappush(pq, (dist[neighbor], neighbor))
16        return dist
17
18    graph = {i: [] for i in range(n)}
19    for a, b, w in edges:
20        graph[a].append((b, w))
21        graph[b].append((a, w))
22
23    dist = dijkstra(source, graph)
24    if dist[destination] >= target:
25        return []
26
27    diff = target - dist[destination]
28    negative_edges = [i for i, (a, b, w) in enumerate(edges) if w == -1]
29    num_neg_edges = len(negative_edges)
30    if num_neg_edges == 0:
31        return []
32
33    weight_per_edge = diff // num_neg_edges
34    remaining_weight = diff % num_neg_edges
35
36    for idx in negative_edges:
37        edges[idx][2] = weight_per_edge + (1 if remaining_weight > 0 else 0)
38        remaining_weight -= 1
39
40    return edges

ℹ

Complexity note: The optimal solution runs in O(n log n) due to Dijkstra's algorithm, which is efficient for finding the shortest path in graphs.

1The shortest path must be calculated first to understand how much adjustment is needed.
2Negative weights can be strategically assigned to meet the target distance.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.