Shortest path algorithms (Dijkstra, Bellman-Ford), MST (Prim's, Kruskal's), and Euler paths (Hierholzer's). These require deeper graph algorithm knowledge.
Problems: 6
Easy: 0
Medium: 3
Hard: 3
Learning approach: Read the problem. Try the test cases yourself first.
Click Hint if stuck — it guides without spoiling.
Use Show Solution only after a genuine attempt.
Then hit Let's Code to run your solution live.
Given list of airline tickets [from, to], reconstruct the itinerary starting from 'JFK'. Use all tickets exactly once. If multiple valid itineraries exist, return the lexicographically smallest.
Sort destinations for each airport. DFS: when you reach a dead end, add the airport to the result. Reverse at the end.
Python Solution
from collections import defaultdict
def findItinerary(tickets):
graph = defaultdict(list)
for src, dst in sorted(tickets, reverse=True):
graph[src].append(dst)
result = []
def dfs(airport):
while graph[airport]:
dfs(graph[airport].pop())
result.append(airport)
dfs('JFK')
return result[::-1]
Key idea: Hierholzer's algorithm for Euler paths. Sort edges in reverse so we pop lexicographically smaller first. Post-order append creates the path in reverse.
Use Prim's algorithm: greedily expand the MST by always picking the cheapest edge connecting a new node.
Python Solution
import heapq
def minCostConnectPoints(points):
n = len(points)
visited = set()
heap = [(0, 0)] # (cost, point_index)
total = 0
while len(visited) < n:
cost, i = heapq.heappop(heap)
if i in visited:
continue
visited.add(i)
total += cost
for j in range(n):
if j not in visited:
dist = (abs(points[i][0] - points[j][0])
+ abs(points[i][1] - points[j][1]))
heapq.heappush(heap, (dist, j))
return total
Key idea: Prim's MST. Start from any node. Greedily pick the cheapest connection to an unvisited node. Repeat until all nodes are in the MST.
Given weighted directed graph, a source node k, and n nodes, find the minimum time for all nodes to receive the signal from k. Return -1 if not all nodes are reachable.
Find shortest paths from k to all other nodes using Dijkstra's. The answer is the maximum shortest path (the last node to receive the signal).
Python Solution
import heapq
from collections import defaultdict
def networkDelayTime(times, n, k):
graph = defaultdict(list)
for u, v, w in times:
graph[u].append((v, w))
dist = {}
heap = [(0, k)]
while heap:
d, node = heapq.heappop(heap)
if node in dist:
continue
dist[node] = d
for neighbor, w in graph[node]:
if neighbor not in dist:
heapq.heappush(heap, (d + w, neighbor))
return max(dist.values()) if len(dist) == n else -1
Key idea: Dijkstra's from source k. The signal delay to all nodes is the max of the shortest path distances. If any node is unreachable, return -1.
Given n×n grid where grid[i][j] is the elevation, find the least time t such that there exists a path from (0,0) to (n-1,n-1) through cells with elevation ≤ t.
Find the path from (0,0) to (n-1,n-1) that minimizes the maximum elevation encountered. Use a min-heap prioritized by the max elevation seen so far.
Python Solution
import heapq
def swimInWater(grid):
n = len(grid)
heap = [(grid[0][0], 0, 0)]
visited = set()
while heap:
t, r, c = heapq.heappop(heap)
if (r, c) in visited:
continue
visited.add((r, c))
if r == n - 1 and c == n - 1:
return t
for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
nr, nc = r+dr, c+dc
if 0 <= nr < n and 0 <= nc < n and (nr,nc) not in visited:
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
Key idea: Modified Dijkstra where the 'distance' is the maximum elevation on the path. At each step, pick the cell that minimizes the peak elevation seen so far.
Compare adjacent words to extract ordering constraints (which letter comes before which). Then topological sort the constraint graph.
Python Solution
from collections import defaultdict, deque
def alienOrder(words):
graph = defaultdict(set)
in_degree = {ch: 0 for word in words for ch in word}
for i in range(len(words) - 1):
w1, w2 = words[i], words[i+1]
min_len = min(len(w1), len(w2))
if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
return "" # invalid: longer word before prefix
for j in range(min_len):
if w1[j] != w2[j]:
if w2[j] not in graph[w1[j]]:
graph[w1[j]].add(w2[j])
in_degree[w2[j]] += 1
break
queue = deque(ch for ch in in_degree if in_degree[ch] == 0)
result = []
while queue:
ch = queue.popleft()
result.append(ch)
for neighbor in graph[ch]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return ''.join(result) if len(result) == len(in_degree) else ""
Key idea: Extract ordering constraints by comparing adjacent word pairs. Use Kahn's topological sort to find a valid character order. If a cycle exists, return empty string.
Time: O(C) total chars. Space: O(1) — at most 26 chars.
Bellman-Ford k+1 iterationscopy prices each roundO(k·E)
Run Bellman-Ford for exactly k+1 rounds (at most k stops = at most k+1 edges). Use a temp copy each round to prevent using more than one edge per round.
Python Solution
def findCheapestPrice(n, flights, src, dst, k):
prices = [float('inf')] * n
prices[src] = 0
for _ in range(k + 1): # at most k+1 edges = k stops
temp = prices[:]
for u, v, w in flights:
if prices[u] != float('inf') and prices[u] + w < temp[v]:
temp[v] = prices[u] + w
prices = temp
return -1 if prices[dst] == float('inf') else prices[dst]
Key idea: Bellman-Ford modified to allow exactly k+1 relaxation rounds. Using a copy of prices ensures we only use one new edge per round — preventing multi-hop shortcuts in a single iteration.