Scale Engineer

Design Graph With Shortest Path Calculator

Hard
#2402Time: - `Graph()`: O(E), where E is the initial number of edges. - `addEdge()`: O(1). - `shortestPath()`: O(E' log n), where E' is the current number of edges. In the worst case, E' is O(n^2), making the complexity O(n^2 log n).Space: O(n + E'), where `n` is the number of nodes and `E'` is the current number of edges. This space is used for the adjacency list.2 companies
Patterns
Design
Algorithms
Shortest Path
Data structures
Heap (Priority Queue)Graph
Companies
SamsungNike

Prompt

There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [fromi, toi, edgeCosti] meaning that there is an edge from fromi to toi with the cost edgeCosti.

Implement the Graph class:

  • Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
  • addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
  • int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.

 

Example 1:

Input
["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
[[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
Output
[null, 6, -1, null, 6]

Explanation
Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6.
g.shortestPath(0, 3); // return -1. There is no path from 0 to 3.
g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above.
g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.

 

Constraints:

  • 1 <= n <= 100
  • 0 <= edges.length <= n * (n - 1)
  • edges[i].length == edge.length == 3
  • 0 <= fromi, toi, from, to, node1, node2 <= n - 1
  • 1 <= edgeCosti, edgeCost <= 106
  • There are no repeated edges and no self-loops in the graph at any point.
  • At most 100 calls will be made for addEdge.
  • At most 100 calls will be made for shortestPath.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach calculates the shortest path only when the shortestPath method is called. It uses an adjacency list to represent the graph, which is efficient for storing graph structures. Adding a new edge is a very fast operation. The main computation happens inside the shortestPath method, where Dijkstra's algorithm is run from the source node to find the shortest path to the destination node.

Algorithm

  • Graph(n, edges):
    1. Create an adjacency list adj of size n.
    2. For each edge (u, v, w) in the input edges, add a pair (v, w) to the list adj[u].
  • addEdge(edge):
    1. Given a new edge (u, v, w), add the pair (v, w) to the list adj[u].
  • shortestPath(node1, node2):
    1. Initialize a distances array of size n with infinity, and set distances[node1] = 0.
    2. Create a priority queue pq to store pairs of (cost, node), ordered by cost.
    3. Add (0, node1) to pq.
    4. While pq is not empty: a. Extract the node u with the smallest cost d from pq. b. If u is the destination node2, return d. c. If d is greater than the already known distance to u, skip. d. For each neighbor v of u with edge weight w: i. If a shorter path is found (distances[u] + w < distances[v]): - Update distances[v] = distances[u] + w. - Add (distances[v], v) to pq.
    5. If the loop completes and node2 was not reached, return -1.

Walkthrough

The graph is stored using an adjacency list, where for each node, we store a list of its outgoing edges and their costs. A List<List<int[]>> is a suitable data structure, where adj.get(u) contains pairs of [v, cost] for all edges from u to v.

Initialization (Graph constructor):

  1. Create an empty adjacency list for n nodes.
  2. Iterate through the initial edges array and populate the adjacency list. For each edge [from, to, cost], add [to, cost] to the list for from.

Adding an Edge (addEdge):

  1. This is a simple and fast operation. Given an edge [from, to, cost], just add [to, cost] to the adjacency list of the from node.

Finding Shortest Path (shortestPath):

  1. This is where the main work is done. We run Dijkstra's algorithm starting from node1.
  2. We need a priority queue to efficiently retrieve the node with the smallest distance to visit next. The priority queue will store pairs of [cost, node].
  3. We also need a distances array to keep track of the minimum cost found so far from node1 to every other node. Initialize all distances to infinity, except for distances[node1], which is 0.
  4. Start by adding [0, node1] to the priority queue.
  5. While the priority queue is not empty, extract the node u with the minimum cost. If this node is the destination, we have found the shortest path.
  6. For each neighbor v of u, if a shorter path to v is found (i.e., distances[u] + cost(u,v) < distances[v]), update distances[v] and add [distances[v], v] to the priority queue.
  7. After the algorithm terminates, if the destination was reached, its distance is returned. Otherwise, no path exists, and we return -1.
import java.util.*; class Graph {    private int n;    private List<List<int[]>> adj;     public Graph(int n, int[][] edges) {        this.n = n;        adj = new ArrayList<>(n);        for (int i = 0; i < n; i++) {            adj.add(new ArrayList<>());        }        for (int[] edge : edges) {            adj.get(edge[0]).add(new int[]{edge[1], edge[2]});        }    }        public void addEdge(int[] edge) {        adj.get(edge[0]).add(new int[]{edge[1], edge[2]});    }        public int shortestPath(int node1, int node2) {        int[] dist = new int[n];        Arrays.fill(dist, Integer.MAX_VALUE);        dist[node1] = 0;         // PriorityQueue stores {distance, node}        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));        pq.offer(new int[]{0, node1});         while (!pq.isEmpty()) {            int[] current = pq.poll();            int d = current[0];            int u = current[1];             if (u == node2) {                return d;            }             if (d > dist[u]) {                continue;            }             for (int[] edge : adj.get(u)) {                int v = edge[0];                int weight = edge[1];                if (dist[u] + weight < dist[v]) {                    dist[v] = dist[u] + weight;                    pq.offer(new int[]{dist[v], v});                }            }        }         return -1;    }}

Complexity

Time

- `Graph()`: O(E), where E is the initial number of edges. - `addEdge()`: O(1). - `shortestPath()`: O(E' log n), where E' is the current number of edges. In the worst case, E' is O(n^2), making the complexity O(n^2 log n).

Space

O(n + E'), where `n` is the number of nodes and `E'` is the current number of edges. This space is used for the adjacency list.

Trade-offs

Pros

  • addEdge is very fast, taking constant time O(1).

  • Space-efficient for sparse graphs, as it only stores existing edges.

  • Conceptually straightforward if Dijkstra's algorithm is familiar.

Cons

  • shortestPath can be slow if called frequently, as it re-computes paths from scratch every time.

  • For dense graphs, the performance degrades to O(n^2 log n) per query, which can be slower than other approaches for the given constraints.

Solutions

public class Graph { private int n ; private int [][] g ; private readonly int inf = 1 << 29 ; public Graph ( int n , int [][] edges ) { this . n = n ; g = new int [ n ][]; for ( int i = 0 ; i < n ; i ++) { g [ i ] = new int [ n ]; for ( int j = 0 ; j < n ; j ++) { g [ i ][ j ] = inf ; } } foreach ( int [] e in edges ) { g [ e [ 0 ]][ e [ 1 ]] = e [ 2 ]; } } public void AddEdge ( int [] edge ) { g [ edge [ 0 ]][ edge [ 1 ]] = edge [ 2 ]; } public int ShortestPath ( int node1 , int node2 ) { int [] dist = new int [ n ]; bool [] vis = new bool [ n ]; Array . Fill ( dist , inf ); dist [ node1 ] = 0 ; for ( int i = 0 ; i < n ; i ++) { int t = - 1 ; for ( int j = 0 ; j < n ; j ++) { if (! vis [ j ] && ( t == - 1 || dist [ t ] > dist [ j ])) t = j ; } vis [ t ] = true ; for ( int j = 0 ; j < n ; j ++) { dist [ j ] = Math . Min ( dist [ j ], dist [ t ] + g [ t ][ j ]); } } return dist [ node2 ] >= inf ? - 1 : dist [ node2 ]; } } /** * Your Graph object will be instantiated and called as such: * Graph obj = new Graph(n, edges); * obj.AddEdge(edge); * int param_2 = obj.ShortestPath(node1,node2); */

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem