Leetcode #2714: Find Shortest Path with K Hops
In this guide, we solve Leetcode #2714 Find Shortest Path with K Hops in Python and focus on the core idea that makes the solution efficient.
You will see the intuition, the step-by-step method, and a clean Python implementation you can use in interviews.
Problem Statement
You are given a positive integer n which is the number of nodes of a 0-indexed undirected weighted connected graph and a 0-indexed 2D array edges where edges[i] = [ui, vi, wi] indicates that there is an edge between nodes ui and vi with weight wi. You are also given two nodes s and d, and a positive integer k, your task is to find the shortest path from s to d, but you can hop over at most k edges.
Quick Facts
- Difficulty: Hard
- Premium: Yes
- Tags: Graph, Shortest Path, Heap (Priority Queue)
Intuition
We need to repeatedly access the smallest or largest element as the input changes.
A heap provides fast insertions and removals while keeping order.
Approach
Push candidates into the heap as you scan, and pop when you need the best element.
Keep the heap size bounded if the problem requires a top-k structure.
Steps:
- Push candidates into a heap.
- Pop the best candidate when needed.
- Maintain heap size or invariants.
Example
Input: n = 4, edges = [[0,1,4],[0,2,2],[2,3,6]], s = 1, d = 3, k = 2
Output: 2
Explanation: In this example there is only one path from node 1 (the green node) to node 3 (the red node), which is (1->0->2->3) and the length of it is 4 + 2 + 6 = 12. Now we can make weight of two edges 0, we make weight of the blue edges 0, then we have 0 + 2 + 0 = 2. It can be shown that 2 is the minimum length of a path we can achieve with the given condition.
Python Solution
class Solution:
def shortestPathWithHops(
self, n: int, edges: List[List[int]], s: int, d: int, k: int
) -> int:
g = [[] for _ in range(n)]
for u, v, w in edges:
g[u].append((v, w))
g[v].append((u, w))
dist = [[inf] * (k + 1) for _ in range(n)]
dist[s][0] = 0
pq = [(0, s, 0)]
while pq:
dis, u, t = heappop(pq)
for v, w in g[u]:
if t + 1 <= k and dist[v][t + 1] > dis:
dist[v][t + 1] = dis
heappush(pq, (dis, v, t + 1))
if dist[v][t] > dis + w:
dist[v][t] = dis + w
heappush(pq, (dis + w, v, t))
return int(min(dist[d]))
Complexity
The time complexity is , and the space complexity is , where represents the number of nodes and represents the maximum number of edges crossed. The space complexity is , where represents the number of nodes and represents the maximum number of edges crossed.
Edge Cases and Pitfalls
Watch for boundary values, empty inputs, and duplicate values where applicable. If the problem involves ordering or constraints, confirm the invariant is preserved at every step.
Summary
This Python solution focuses on the essential structure of the problem and keeps the implementation interview-friendly while meeting the constraints.