NeetCode 150 · Advanced Graphs

Advanced Graphs Problems

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.
01 Hard DFSGraphEuler Path
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.
Test Cases
findItinerary([['MUC','LHR'],['JFK','MUC'],['SFO','SJC'],['LHR','SFO']]) → ['JFK','MUC','LHR','SFO','SJC']
Hierholzer's DFSsort destinationspost-order append reverse
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.
Time: O(E log E) — sort dominates.
Space: O(E).
02 Medium ArrayGraphUnion FindMST
Given array of points, find minimum cost to connect all using Manhattan distance edges. Cost = sum of distances in the minimum spanning tree.
Test Cases
minCostConnectPoints([[0,0],[2,2],[3,10],[5,2],[7,0]]) → 20
Prim's MSTmin heapO(n² log n)
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.
Time: O(n² log n).
Space: O(n²).
03 Medium DFSBFSGraphShortest Path
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.
Test Cases
networkDelayTime([[2,1,1],[2,3,1],[3,4,1]], 4, 2) → 2 networkDelayTime([[1,2,1]], 2, 1) → -1
Dijkstra'smin heapO((V+E) log V)
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.
Time: O((V+E) log V).
Space: O(V+E).
04 Hard ArrayBinary SearchDFSBFSHeap
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.
Test Cases
swimInWater([[0,2],[1,3]]) → 3 swimInWater([[0,1,2,3,4],[24,23,22,21,5],[12,13,14,15,16],[11,17,18,19,20],[10,9,8,7,6]]) → 16
Dijkstra min-max pathheap bottleneckO(n² log n)
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.
Time: O(n² log n).
Space: O(n²).
05 Hard ArrayStringDFSBFSTopological Sort
Given words sorted lexicographically in an alien language, derive the character ordering. Return any valid order, or empty string if invalid.
Test Cases
alienOrder(['wrt','wrf','er','ett','rftt']) → 'wertf' (or other valid topological order) alienOrder(['z','x']) → 'zx'
pairwise comparisontopological sortO(C) C=total chars
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.
06 Medium DFSBFSGraphDPShortest Path
Given n cities, flights [from, to, price], source src, destination dst, and max stops k, find cheapest price from src to dst with at most k stops.
Test Cases
findCheapestPrice(4,[[0,1,100],[1,2,100],[2,0,100],[1,3,600],[2,3,200]],0,3,1) → 700
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.
Time: O(k·E).
Space: O(n).
← Prev Category Next Category →