Facebook Pixel

2699. Modify Graph Edge Weights

HardGraphShortest PathHeap (Priority Queue)
Leetcode Link

Problem Description

You have an undirected weighted connected graph with n nodes (labeled from 0 to n - 1). The graph is defined by an array edges where each element edges[i] = [ai, bi, wi] represents an edge between nodes ai and bi with weight wi.

The graph has two types of edges:

  • Some edges have a weight of -1 (these are modifiable)
  • Other edges have positive weights (these cannot be modified)

Your task is to assign positive integer values (in the range [1, 2 * 10^9]) to all edges with weight -1 such that the shortest distance from a given source node to a destination node becomes exactly equal to a given target value.

The problem asks you to:

  • Modify all -1 weight edges by assigning them positive values
  • Ensure the shortest path from source to destination equals target after modification
  • Return the modified edge list if such a modification is possible
  • Return an empty array if it's impossible to achieve the target distance

Important constraints:

  • You cannot modify edges that already have positive weights
  • The graph is connected (there's a path between any two nodes)
  • If multiple valid modifications exist, any one is acceptable
  • All -1 edges must be assigned a value (you can't leave any as -1)

The output should be an array containing all edges (both modified and unmodified) in any order if a valid solution exists, or an empty array if no solution is possible.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The key insight is to understand what happens when we ignore the -1 edges initially and compute the shortest path using only the positive weight edges.

Let's denote this initial shortest distance as d. Three scenarios can occur:

Scenario 1: d < target
If we already have a path shorter than the target using only positive edges, we're in trouble. Since we can only add edges (by converting -1 edges to positive values), we can never make the shortest path longer. Adding edges can only maintain or decrease the shortest path distance. Therefore, it's impossible to achieve the target.

Scenario 2: d = target
Perfect! We already have a shortest path of exactly the target length using only positive edges. To maintain this, we simply set all -1 edges to a very large value (like 2 * 10^9) so they won't be used in any shortest path. The existing shortest path remains unchanged.

Scenario 3: d > target
This is the interesting case. Currently, our shortest path is too long, so we need to create a shorter path by strategically using the -1 edges. The strategy is to add -1 edges one by one and see if they can help us achieve the target.

For each -1 edge, we:

  1. Temporarily set its weight to 1 (the minimum possible positive value)
  2. Compute the new shortest path distance
  3. If this new path is ≤ target, we know this edge is critical for achieving our goal

When we find such a critical edge, we can fine-tune its weight. If the shortest path with this edge weighted as 1 gives us distance d', and d' < target, we can increase the edge weight by exactly target - d' to make the shortest path exactly target. All remaining -1 edges can then be set to the maximum value.

The greedy approach works because once we find a path that can be adjusted to match the target, we don't need to consider other -1 edges for the shortest path - we can safely set them to maximum values.

Learn more about Graph, Shortest Path and Heap (Priority Queue) patterns.

Solution Approach

The solution implements the intuition using Dijkstra's algorithm as the core component for finding shortest paths. Here's the step-by-step implementation:

1. Helper Function - Dijkstra's Algorithm

First, we implement a helper function dijkstra(edges) that computes the shortest distance from source to destination:

  • Create an adjacency matrix g of size n × n, initialized with inf (infinity)
  • Populate the matrix with edge weights, ignoring edges with weight -1
  • Use the standard Dijkstra's algorithm with a distance array dist and visited array vis
  • Return the shortest distance to the destination node

2. Initial Check Without -1 Edges

d = dijkstra(edges)
if d < target:
    return []

We first compute the shortest path using only positive weight edges. If this distance is already less than target, it's impossible to achieve the target (as explained in the intuition), so we return an empty array.

3. Handle the Case When d == target

ok = d == target

We set a flag ok to track whether we've successfully achieved the target distance.

4. Process Each -1 Edge

For each edge in the graph:

  • Skip edges with positive weights (they can't be modified)
  • If we've already achieved the target (ok = True), set all remaining -1 edges to inf (2 × 10^9)
  • Otherwise, try setting the current -1 edge to weight 1:
e[2] = 1
d = dijkstra(edges)
if d <= target:
    ok = True
    e[2] += target - d

When we find an edge that creates a path ≤ target:

  • Set ok = True to indicate success
  • Adjust the edge weight by adding target - d to make the shortest path exactly equal to target
  • The weight becomes 1 + (target - d) = target - d + 1

5. Return Result

return edges if ok else []

Return the modified edges array if we successfully achieved the target distance, otherwise return an empty array.

Key Implementation Details:

  • The algorithm uses a greedy approach: once we find a way to achieve the target, we stop trying to optimize further -1 edges
  • Setting unused -1 edges to inf ensures they won't interfere with the shortest path
  • The time complexity is O(k × n²) where k is the number of -1 edges and n is the number of nodes, due to running Dijkstra's algorithm multiple times
  • The space complexity is O(n²) for the adjacency matrix representation

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's walk through a concrete example to illustrate the solution approach.

Example Setup:

  • Graph with 4 nodes (0, 1, 2, 3)
  • Edges: [[0,1,5], [1,2,-1], [2,3,2], [0,3,9]]
  • Source: 0, Destination: 3, Target: 7

Step 1: Initial Check (Ignore -1 edges)

First, we run Dijkstra using only positive weight edges:

  • Available edges: [0,1,5], [2,3,2], [0,3,9]
  • Shortest paths from node 0:
    • To node 1: 5 (direct edge)
    • To node 2: ∞ (no path without the -1 edge)
    • To node 3: 9 (direct edge)

Initial shortest distance d = 9. Since 9 > 7 (target), we continue.

Step 2: Process the -1 Edge

We iterate through edges and find [1,2,-1]:

  • Temporarily set weight to 1: [1,2,1]
  • Run Dijkstra with all edges now:
    • Path 0→1: 5
    • Path 0→1→2: 5+1 = 6
    • Path 0→1→2→3: 5+1+2 = 8
    • Path 0→3: 9 (direct)

New shortest distance d' = 8. Since 8 > 7, this doesn't help yet.

Wait, let's reconsider - if d' = 8 with weight 1, we need a shorter path. Let's check if we made an error...

Actually, with the edge at weight 1, the shortest path is 8, which is still > target. The algorithm would continue, but since this is our only -1 edge and it doesn't give us d' ≤ target with weight 1, the problem has no solution.

Alternative Example (Successful Case):

Let's modify the example slightly:

  • Edges: [[0,1,4], [1,2,-1], [2,3,1], [0,3,9]]
  • Source: 0, Destination: 3, Target: 8

Step 1: Initial Check

  • Without -1 edge: shortest path is 9 (0→3 direct)
  • Since 9 > 8, we continue

Step 2: Process the -1 Edge

  • Set [1,2,-1] to [1,2,1]
  • New shortest path: 0→1→2→3 = 4+1+1 = 6
  • Since 6 < 8 (target), we found a critical edge!

Step 3: Adjust the Edge Weight

  • Current shortest distance with weight 1: d' = 6
  • Target = 8
  • Increase edge weight by: target - d' = 8 - 6 = 2
  • Final edge weight: 1 + 2 = 3

Final Result: [[0,1,4], [1,2,3], [2,3,1], [0,3,9]]

Verification: Shortest path is now 0→1→2→3 = 4+3+1 = 8 ✓

The algorithm successfully modified the -1 edge to weight 3, achieving exactly the target distance of 8.

Solution Implementation

1from typing import List
2from math import inf
3
4class Solution:
5    def modifiedGraphEdges(
6        self, n: int, edges: List[List[int]], source: int, destination: int, target: int
7    ) -> List[List[int]]:
8      
9        def dijkstra(edge_list: List[List[int]]) -> int:
10            """
11            Calculate shortest path from source to destination using Dijkstra's algorithm.
12            Ignores edges with weight -1.
13            """
14            # Build adjacency matrix representation of the graph
15            adjacency_matrix = [[inf] * n for _ in range(n)]
16            for node_a, node_b, weight in edge_list:
17                if weight == -1:
18                    continue  # Skip unassigned edges
19                adjacency_matrix[node_a][node_b] = weight
20                adjacency_matrix[node_b][node_a] = weight  # Undirected graph
21          
22            # Initialize distance array and visited set
23            distances = [inf] * n
24            distances[source] = 0
25            visited = [False] * n
26          
27            # Process all nodes using Dijkstra's algorithm
28            for _ in range(n):
29                # Find unvisited node with minimum distance
30                min_node = -1
31                for node in range(n):
32                    if not visited[node] and (min_node == -1 or distances[min_node] > distances[node]):
33                        min_node = node
34              
35                # Mark as visited
36                visited[min_node] = True
37              
38                # Update distances to neighbors
39                for neighbor in range(n):
40                    distances[neighbor] = min(
41                        distances[neighbor], 
42                        distances[min_node] + adjacency_matrix[min_node][neighbor]
43                    )
44          
45            return distances[destination]
46      
47        # Define a large value for "infinity" weight assignment
48        INFINITY_WEIGHT = 2 * 10**9
49      
50        # Check initial shortest path (ignoring -1 edges)
51        initial_distance = dijkstra(edges)
52      
53        # If shortest path without -1 edges is already less than target, impossible
54        if initial_distance < target:
55            return []
56      
57        # Track if we've achieved the target distance
58        target_achieved = (initial_distance == target)
59      
60        # Process each edge with weight -1
61        for edge in edges:
62            if edge[2] > 0:
63                continue  # Skip already assigned edges
64          
65            if target_achieved:
66                # Already achieved target, set remaining -1 edges to infinity
67                edge[2] = INFINITY_WEIGHT
68                continue
69          
70            # Try assigning weight 1 to this edge
71            edge[2] = 1
72            current_distance = dijkstra(edges)
73          
74            if current_distance <= target:
75                # Can achieve target by adjusting this edge
76                target_achieved = True
77                # Increase edge weight to exactly match target distance
78                edge[2] += target - current_distance
79      
80        # Return modified edges if target achieved, empty list otherwise
81        return edges if target_achieved else []
82
1class Solution {
2    // Maximum value for edge weights that need to be set to "infinity"
3    private final int INF = 2_000_000_000;
4
5    /**
6     * Modifies graph edges with weight -1 to make shortest path from source to destination equal to target.
7     * 
8     * @param n Number of nodes in the graph
9     * @param edges Array of edges where each edge is [node1, node2, weight]
10     * @param source Starting node for shortest path
11     * @param destination Ending node for shortest path
12     * @param target Desired shortest path distance
13     * @return Modified edges array if possible, empty array otherwise
14     */
15    public int[][] modifiedGraphEdges(
16        int n, int[][] edges, int source, int destination, int target) {
17      
18        // Calculate initial shortest path with current edge weights (ignoring -1 edges)
19        long currentDistance = dijkstra(edges, n, source, destination);
20      
21        // If shortest path is already less than target, it's impossible to achieve target
22        if (currentDistance < target) {
23            return new int[0][];
24        }
25      
26        // Check if we've already achieved the target distance
27        boolean targetAchieved = (currentDistance == target);
28      
29        // Process each edge to modify weights of -1 edges
30        for (int[] edge : edges) {
31            // Skip edges that already have positive weights
32            if (edge[2] > 0) {
33                continue;
34            }
35          
36            // If target is already achieved, set remaining -1 edges to infinity
37            if (targetAchieved) {
38                edge[2] = INF;
39                continue;
40            }
41          
42            // Try setting this -1 edge to weight 1
43            edge[2] = 1;
44          
45            // Recalculate shortest path with the new edge weight
46            currentDistance = dijkstra(edges, n, source, destination);
47          
48            // If new distance is at most target, we can achieve target
49            if (currentDistance <= target) {
50                targetAchieved = true;
51                // Adjust edge weight to make shortest path exactly equal to target
52                edge[2] += target - currentDistance;
53            }
54        }
55      
56        // Return modified edges if target achieved, empty array otherwise
57        return targetAchieved ? edges : new int[0][];
58    }
59
60    /**
61     * Calculates shortest path from source to destination using Dijkstra's algorithm.
62     * 
63     * @param edges Array of edges in the graph
64     * @param n Number of nodes
65     * @param source Starting node
66     * @param destination Ending node
67     * @return Shortest distance from source to destination
68     */
69    private long dijkstra(int[][] edges, int n, int source, int destination) {
70        // Initialize adjacency matrix for graph representation
71        int[][] adjacencyMatrix = new int[n][n];
72      
73        // Initialize distances array with infinity
74        long[] distances = new long[n];
75        Arrays.fill(distances, INF);
76        distances[source] = 0;
77      
78        // Fill adjacency matrix with infinity initially
79        for (int[] row : adjacencyMatrix) {
80            Arrays.fill(row, INF);
81        }
82      
83        // Build adjacency matrix from edges (undirected graph)
84        for (int[] edge : edges) {
85            int nodeA = edge[0];
86            int nodeB = edge[1];
87            int weight = edge[2];
88          
89            // Skip edges with weight -1 (not yet assigned)
90            if (weight == -1) {
91                continue;
92            }
93          
94            // Add undirected edge to adjacency matrix
95            adjacencyMatrix[nodeA][nodeB] = weight;
96            adjacencyMatrix[nodeB][nodeA] = weight;
97        }
98      
99        // Track visited nodes
100        boolean[] visited = new boolean[n];
101      
102        // Dijkstra's algorithm main loop
103        for (int i = 0; i < n; i++) {
104            // Find unvisited node with minimum distance
105            int minNode = -1;
106            for (int j = 0; j < n; j++) {
107                if (!visited[j] && (minNode == -1 || distances[minNode] > distances[j])) {
108                    minNode = j;
109                }
110            }
111          
112            // Mark node as visited
113            visited[minNode] = true;
114          
115            // Update distances to all neighbors
116            for (int j = 0; j < n; j++) {
117                distances[j] = Math.min(distances[j], distances[minNode] + adjacencyMatrix[minNode][j]);
118            }
119        }
120      
121        return distances[destination];
122    }
123}
124
1using ll = long long;
2const int INF = 2e9;
3
4class Solution {
5public:
6    vector<vector<int>> modifiedGraphEdges(int n, vector<vector<int>>& edges, int source, int destination, int target) {
7        // Calculate initial shortest distance (ignoring edges with weight -1)
8        ll shortestDistance = dijkstra(edges, n, source, destination);
9      
10        // If shortest path is already less than target, impossible to achieve target
11        if (shortestDistance < target) {
12            return {};
13        }
14      
15        // Check if we already achieved the target distance
16        bool targetAchieved = (shortestDistance == target);
17      
18        // Process each edge to modify weights
19        for (auto& edge : edges) {
20            // Skip edges that already have positive weights
21            if (edge[2] > 0) {
22                continue;
23            }
24          
25            // If target already achieved, set remaining -1 edges to maximum value
26            if (targetAchieved) {
27                edge[2] = INF;
28                continue;
29            }
30          
31            // Try setting current -1 edge to weight 1
32            edge[2] = 1;
33            shortestDistance = dijkstra(edges, n, source, destination);
34          
35            // If new shortest path is at most target, we can achieve target
36            if (shortestDistance <= target) {
37                targetAchieved = true;
38                // Adjust weight to exactly achieve target distance
39                edge[2] += target - shortestDistance;
40            }
41        }
42      
43        // Return modified edges if target achieved, empty vector otherwise
44        return targetAchieved ? edges : vector<vector<int>>{};
45    }
46
47private:
48    ll dijkstra(vector<vector<int>>& edges, int n, int source, int destination) {
49        // Initialize adjacency matrix
50        ll adjacencyMatrix[n][n];
51        ll distance[n];
52        bool visited[n];
53      
54        // Set up initial values
55        for (int i = 0; i < n; ++i) {
56            fill(adjacencyMatrix[i], adjacencyMatrix[i] + n, INF);
57            distance[i] = INF;
58            visited[i] = false;
59        }
60      
61        // Source node has distance 0 to itself
62        distance[source] = 0;
63      
64        // Build adjacency matrix from edges (skip -1 weight edges)
65        for (const auto& edge : edges) {
66            int nodeA = edge[0];
67            int nodeB = edge[1];
68            int weight = edge[2];
69          
70            // Skip edges with weight -1 (unmodified edges)
71            if (weight == -1) {
72                continue;
73            }
74          
75            // Update bidirectional edge weights
76            adjacencyMatrix[nodeA][nodeB] = weight;
77            adjacencyMatrix[nodeB][nodeA] = weight;
78        }
79      
80        // Dijkstra's algorithm implementation
81        for (int i = 0; i < n; ++i) {
82            // Find unvisited node with minimum distance
83            int minNode = -1;
84            for (int j = 0; j < n; ++j) {
85                if (!visited[j] && (minNode == -1 || distance[j] < distance[minNode])) {
86                    minNode = j;
87                }
88            }
89          
90            // Mark current minimum node as visited
91            visited[minNode] = true;
92          
93            // Update distances to all neighbors
94            for (int j = 0; j < n; ++j) {
95                distance[j] = min(distance[j], distance[minNode] + adjacencyMatrix[minNode][j]);
96            }
97        }
98      
99        // Return shortest distance to destination
100        return distance[destination];
101    }
102};
103
1/**
2 * Modifies graph edges with weight -1 to achieve exactly the target distance from source to destination.
3 * Returns modified edges if possible, empty array otherwise.
4 * 
5 * @param n - Number of nodes in the graph
6 * @param edges - Array of edges [nodeA, nodeB, weight], where -1 means modifiable weight
7 * @param source - Starting node
8 * @param destination - Target node
9 * @param target - Desired shortest path distance
10 * @returns Modified edges array or empty array if impossible
11 */
12function modifiedGraphEdges(
13    n: number,
14    edges: number[][],
15    source: number,
16    destination: number,
17    target: number,
18): number[][] {
19    const INFINITY = 2e9;
20  
21    /**
22     * Calculates shortest path from source to destination using Dijkstra's algorithm.
23     * Ignores edges with weight -1.
24     * 
25     * @param edges - Current state of edges
26     * @returns Shortest distance from source to destination
27     */
28    const dijkstra = (edges: number[][]): number => {
29        // Initialize adjacency matrix with infinite distances
30        const adjacencyMatrix: number[][] = Array(n)
31            .fill(0)
32            .map(() => Array(n).fill(INFINITY));
33      
34        // Initialize distance array and visited tracking
35        const distances: number[] = Array(n).fill(INFINITY);
36        const visited: boolean[] = Array(n).fill(false);
37      
38        // Build adjacency matrix from edges (undirected graph)
39        for (const [nodeA, nodeB, weight] of edges) {
40            // Skip edges with unassigned weight
41            if (weight === -1) {
42                continue;
43            }
44            adjacencyMatrix[nodeA][nodeB] = weight;
45            adjacencyMatrix[nodeB][nodeA] = weight;
46        }
47      
48        // Set source distance to 0
49        distances[source] = 0;
50      
51        // Process all nodes using Dijkstra's algorithm
52        for (let i = 0; i < n; ++i) {
53            // Find unvisited node with minimum distance
54            let minNode = -1;
55            for (let j = 0; j < n; ++j) {
56                if (!visited[j] && (minNode === -1 || distances[j] < distances[minNode])) {
57                    minNode = j;
58                }
59            }
60          
61            // Mark current node as visited
62            visited[minNode] = true;
63          
64            // Update distances to all neighbors
65            for (let j = 0; j < n; ++j) {
66                distances[j] = Math.min(distances[j], distances[minNode] + adjacencyMatrix[minNode][j]);
67            }
68        }
69      
70        return distances[destination];
71    };
72  
73    // Calculate initial shortest distance with existing positive weights
74    let currentDistance = dijkstra(edges);
75  
76    // If current distance is already less than target, impossible to achieve target
77    if (currentDistance < target) {
78        return [];
79    }
80  
81    // Check if we've already achieved the target distance
82    let targetAchieved = currentDistance === target;
83  
84    // Process each edge with weight -1
85    for (const edge of edges) {
86        // Skip edges with already assigned positive weights
87        if (edge[2] > 0) {
88            continue;
89        }
90      
91        // If target already achieved, set remaining -1 edges to infinity
92        if (targetAchieved) {
93            edge[2] = INFINITY;
94            continue;
95        }
96      
97        // Try setting current edge weight to 1
98        edge[2] = 1;
99        currentDistance = dijkstra(edges);
100      
101        // If this brings us to or below target, adjust weight accordingly
102        if (currentDistance <= target) {
103            targetAchieved = true;
104            // Add extra weight to achieve exactly the target distance
105            edge[2] += target - currentDistance;
106        }
107    }
108  
109    // Return modified edges if target achieved, empty array otherwise
110    return targetAchieved ? edges : [];
111}
112

Time and Space Complexity

Time Complexity: O(n^3)

The time complexity is dominated by the Dijkstra's algorithm implementation and how many times it's called:

  1. The dijkstra function has a time complexity of O(n^2):

    • Building the adjacency matrix takes O(|edges|) time, where |edges| ≤ n^2
    • The main Dijkstra loop runs n iterations
    • In each iteration, finding the minimum unvisited node takes O(n) time
    • Updating distances for all neighbors takes O(n) time
    • Total for one Dijkstra call: O(n^2)

  2. In the worst case, dijkstra is called O(n) times:

    • Once initially
    • Up to once for each edge with weight -1
    • Since there can be up to O(n^2) edges total, but the algorithm only processes edges with -1 weight and calls Dijkstra at most once per such edge until ok becomes True
    • However, in the worst case scenario where we need to check many edges, this could be up to O(n) calls

  3. Overall time complexity: O(n) × O(n^2) = O(n^3)

Space Complexity: O(n^2)

The space complexity is determined by:

  1. The adjacency matrix g in the dijkstra function: O(n^2)
  2. The distance array dist: O(n)
  3. The visited array vis: O(n)
  4. The input edges list storage: O(|edges|) where |edges| ≤ n^2

The dominant factor is the adjacency matrix with O(n^2) space, making the total space complexity O(n^2).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Not Handling the Case When Initial Path Already Exceeds Target

Pitfall: A common mistake is assuming that if the initial shortest path (using only positive edges) equals the target, we're done and can simply set all -1 edges to infinity. This overlooks the fact that adding -1 edges with small weights might create a shorter path.

Example Scenario:

  • Initial shortest path using only positive edges: 10
  • Target: 10
  • There exists a -1 edge that could create a path of length 8

If we simply set all -1 edges to infinity when initial_distance == target, we miss the opportunity to properly handle this case.

Solution: The code correctly handles this by continuing to process -1 edges even when initial_distance == target. It only sets remaining -1 edges to infinity after confirming that at least one path configuration achieves the target.

2. Integer Overflow When Setting Edge Weights

Pitfall: When adjusting an edge weight using edge[2] += target - current_distance, if target - current_distance is very large, the resulting weight might exceed the allowed maximum of 2 × 10^9.

Example:

  • Current distance after setting edge to 1: 5
  • Target: 2,000,000,010
  • Required adjustment: 2,000,000,005
  • Final edge weight: 2,000,000,006 (exceeds the limit)

Solution: Add a validation check after weight adjustment:

if current_distance <= target:
    target_achieved = True
    new_weight = 1 + (target - current_distance)
    # Ensure weight doesn't exceed maximum allowed value
    if new_weight > INFINITY_WEIGHT:
        return []  # Impossible to achieve target within constraints
    edge[2] = new_weight

3. Incorrectly Assuming First Valid Edge is Optimal

Pitfall: The greedy approach of using the first -1 edge that allows achieving the target might not always work if that edge, when adjusted, blocks other critical paths.

Example: Consider a graph where:

  • Path A uses edge X and has length 8
  • Path B doesn't use edge X and has length 12
  • Target is 10

Setting edge X to make Path A equal 10 might inadvertently make Path B shorter than 10 through edge X, creating a new shortest path less than the target.

Solution: After finding a potential solution, verify that the final configuration actually achieves the target:

# After processing all edges, do a final verification
if target_achieved:
    final_distance = dijkstra(edges)
    if final_distance != target:
        return []  # Configuration doesn't achieve target
    return edges
return []

4. Not Preserving Edge Order or Original References

Pitfall: Some implementations might create new edge lists or reorder edges, which can cause issues if the problem expects the original edge order or if there are external references to the edge objects.

Solution: The current implementation correctly modifies edges in-place, preserving both order and references. However, if you need to work with a copy to avoid modifying the input:

# Create a deep copy at the start
import copy
edges_copy = copy.deepcopy(edges)
# Work with edges_copy throughout
# Return edges_copy at the end
Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

What is the best way of checking if an element exists in an unsorted array once in terms of time complexity? Select the best that applies.

Recommended Readings

Graph Fundamentals

https assets algo monster cover_photos graph svg Graph Fundamentals Tree with 0 cycle At this point you should be pretty familiar with trees A tree is a special kind of graph a connected acyclic cycle less graph A graph may contain cycle s and nodes could be disconnected A tree

Shortest Path

Shortest Path Between A and B Prereq BFS on Graph problems graph_bfs Given an unweighted connected graph return the length of the shortest path between two nodes A and B in terms of the number of edges Assume there always exists a path between nodes A and B Input graph

Heap Fundamentals

https assets algo monster cover_photos heap svg Priority Queue and Heap What is the relationship between priority queue and heap Priority Queue is an Abstract Data Type and Heap is the concrete data structure we use to implement a priority queue Priority Queue A priority queue is a data structure

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More