Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
When does a given path given priority over another?
What do we need to keep track of during the traversal?
HAPPY CASE
Input: n = 4, flights = [[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]], src = 0, dst = 3, k = 1
Output: 700
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 1
Output: 200
EDGE CASE
Input: n = 3, flights = [[0,1,100],[1,2,100],[0,2,500]], src = 0, dst = 2, k = 0
Output: 500Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For graph problems, some things we want to consider are:
node0 -> node1, we can take path 0->1, with 5 cost and 1 stop, or we could take 0->3->1, with 4 cost and 2 stops. If we update our Dijkstra's shortest path cache to be 4 cost, then we will miss out on a better cost because k = 2 already by taking the shortest path to 1. By taking the shortest cost path to 1 (0->3->1), we already used our 2 stops, so our next node must be our goal of node2 to not violate k constraint. The actual shortest path is 0->1->4->2 where we take a higher cost path to 1, 0->1 cost 5, but k = 1.Plan the solution with appropriate visualizations and pseudocode.
General idea: Need to keep track of the number of stops taken to reach a node (city), in addition to the shortest path from the source node
To implement Dijkstra, we need a priority queue to pop out the lowest weight node for next search.
In this case, the weight would be the accumulated flight cost.
The node takes a form of `(cost, src, k)`. `cost` is the accumulated cost, `src` is the current node's location, `k` is stop times we left as we only have at most K stops. I also convert `edges` to an adjacent list based graph `g`.
Use a `vis` array to maintain visited nodes to avoid loop. `
vis[x]` record the remaining steps to reach x with the lowest cost.
If `vis[x] >= k`, then no need to visit that case `(start from x with k steps left)` as a better solution has been visited before (more remaining step and lower cost as heappopped beforehand).
And we should initialize `vis[x]` to `0` to ensure visit always stop at a negative `k`.
Once `k` is used up (`k == 0`) or `vis[x] >= k`, we no longer push that node `x` to our queue.
Once a popped cost is our destination, we get our lowest valid cost.⚠️ Common Mistakes
prev[v] against prev[u] + cost(u,v). However, in this case we will not get the minimum value of the current state. It's possible that curr_1 < curr_2 < prev but, curr_2 is encountered later than curr_1, resulting in it being overwritten.Implement the code to solve the algorithm.
class Solution {
int UNVISITED = 10000000;
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int k) {
// build graph, pair first element is denoting destination & second element denotes fare
Map<Integer, List<int[]>> graph = buildGraph(flights, n);
int result = dijkstra(graph, src, dst, k, n);
return result;
}
// apply Dijkstra's
public int dijkstra(
Map<Integer, List<int[]>> graph,
int start, int dest, int k, int n
) {
int[] dist = new int[n];
Arrays.fill(dist, UNVISITED);
dist[start] = 0;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> {
if(a[2] == b[2]) return a[1] - b[1]; // if # of stops are equal, sort by cost
return a[2] - b[2]; // otherwise sort first by # of stops
});
pq.offer(new int[]{start, 0, 0});
while(!pq.isEmpty()) {
int[] item = pq.poll();
int node = item[0];
int cost = item[1];
int stops = item[2];
if(stops > k) continue;
List<int[]> neighbors = graph.get(node);
// examine all neighboring edges if possible
for(int[] neighbor : neighbors) {
int neighborNode = neighbor[0];
int neighborCost = neighbor[1];
int totalCost = cost + neighborCost;
// is there a better cost?
if(totalCost < dist[neighborNode]) {
dist[neighborNode] = totalCost;
pq.offer(new int[]{neighborNode, totalCost, stops+1});
}
}
}
return dist[dest] == UNVISITED ? -1 : dist[dest];
}
public Map<Integer, List<int[]>> buildGraph(int[][] flights, int n) {
Map<Integer, List<int[]>> graph = new HashMap<>();
for(int i = 0; i < n; i++) graph.put(i, new ArrayList<>());
for(int[] flight : flights) {
int src = flight[0];
int dest = flight[1];
int cost = flight[2];
graph.get(src).add(new int[]{dest, cost});
}
return graph;
}
}import heapq
class Solution:
def findCheapestPrice(self, n: int, flights: List[List[int]], src: int, dst: int, K: int) -> int:
# Build the adjacency matrix
adj_matrix = [[0 for _ in range(n)] for _ in range(n)]
for s, d, w in flights:
adj_matrix[s][d] = w
# Shortest distances array
distances = [float("inf") for _ in range(n)]
current_stops = [float("inf") for _ in range(n)]
distances[src], current_stops[src] = 0, 0
# Data is (cost, stops, node)
minHeap = [(0, 0, src)]
while minHeap:
cost, stops, node = heapq.heappop(minHeap)
# If destination is reached, return the cost to get here
if node == dst:
return cost
# If there are no more steps left, continue
if stops == K + 1:
continue
# Examine and relax all neighboring edges if possible
for nei in range(n):
if adj_matrix[node][nei] > 0:
dU, dV, wUV = cost, distances[nei], adj_matrix[node][nei]
# Better cost?
if dU + wUV < dV:
distances[nei] = dU + wUV
heapq.heappush(minHeap, (dU + wUV, stops + 1, nei))
current_stops[nei] = stops
elif stops < current_stops[nei]:
# Better steps?
heapq.heappush(minHeap, (dU + wUV, stops + 1, nei))
return -1 if distances[dst] == float("inf") else distances[dst]Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Time Complexity: O(KE), where E is # of edges and K is the # of stops
Space Complexity: O(V), where V is the # of nodes in graph
