Problems
Master shortest path algorithms through these carefully selected problems. Each problem demonstrates different shortest path applications and implementation techniques essential for interviews.
Problem Categories
Easy Problems
1. Network Delay Time
LeetCode 743 | Difficulty: Medium | Acceptance: 53.0%
Problem: You are given a network of n nodes, labeled 0 through n-1. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target. We send a signal from a certain node K. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.
Dijkstra’s Algorithm Approach: Use Dijkstra to find shortest path from source to all nodes, then find maximum time.
Solution Template:
function networkDelayTime(times, n, k) {
// Build graph: adjacency list
const graph = Array.from({length: n + 1}, () => []);
for (const [u, v, w] of times) {
graph[u].push([v, w]);
}
// Dijkstra's algorithm
const distances = new Array(n + 1).fill(Infinity);
distances[k] = 0;
const pq = new MinPriorityQueue();
pq.enqueue(k, 0);
while (!pq.isEmpty()) {
const [node, dist] = pq.dequeue();
if (dist > distances[node]) continue;
for (const [neighbor, weight] of graph[node]) {
const newDist = dist + weight;
if (newDist < distances[neighbor]) {
distances[neighbor] = newDist;
pq.enqueue(neighbor, newDist);
}
}
}
let maxTime = 0;
for (let i = 1; i <= n; i++) {
if (distances[i] === Infinity) return -1;
maxTime = Math.max(maxTime, distances[i]);
}
return maxTime;
}Time Complexity: O((V + E) log V) | Space Complexity: O(V + E)
2. Cheapest Flights Within K Stops
LeetCode 787 | Difficulty: Medium | Acceptance: 35.9%
Problem: There are n cities connected by some number of flights. You are given an array flights where flights[i] = [fromi, toi, pricei] indicates that there is a flight from city fromi to city toi with cost pricei. You are also given three integers src, dst, and k, return the cheapest price from src to dst with at most k stops. If there is no such route, return -1.
Modified Dijkstra with Stop Constraint: Use Dijkstra with additional constraint on number of stops.
Solution Template:
function findCheapestPrice(n, flights, src, dst, k) {
// Build graph
const graph = Array.from({length: n}, () => []);
for (const [from, to, price] of flights) {
graph[from].push([to, price]);
}
// Priority queue: [cost, city, stops]
const pq = new MinPriorityQueue();
pq.enqueue([0, src, 0], 0); // [cost, city, stops], priority = cost
const visited = new Array(n).fill().map(() => new Array(k + 2).fill(Infinity));
while (!pq.isEmpty()) {
const [cost, city, stops] = pq.dequeue().element;
if (city === dst) return cost;
if (stops > k) continue;
if (cost > visited[city][stops]) continue;
visited[city][stops] = cost;
for (const [nextCity, price] of graph[city]) {
const newCost = cost + price;
if (newCost < visited[nextCity][stops + 1]) {
pq.enqueue([newCost, nextCity, stops + 1], newCost);
}
}
}
return -1;
}Time Complexity: O((V + E) log V) | Space Complexity: O(V * K)
Medium Problems
3. Path with Minimum Effort
LeetCode 1631 | Difficulty: Medium | Acceptance: 60.9%
Problem: You are a hiker preparing for an upcoming hike. You are given heights, a 2D array of size rows x columns, where heights[row][col] represents the height of cell (row, col). You are situated in the top-left cell, (0, 0), and you hope to travel to the bottom-right cell, (rows-1, columns-1) (i.e., 0-indexed). You can move up, down, left, right. The “effort” of a path is the maximum absolute difference in heights between any two consecutive cells of the path. Return the minimum effort required to travel from the top-left cell to the bottom-right cell.
Dijkstra with Grid Application: Treat grid as graph where edges represent effort between adjacent cells.
Solution Template:
function minimumEffortPath(heights) {
const rows = heights.length;
const cols = heights[0].length;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
// Priority queue: [effort, row, col]
const pq = new MinPriorityQueue();
pq.enqueue([0, 0, 0], 0);
const efforts = Array.from({length: rows}, () => new Array(cols).fill(Infinity));
efforts[0][0] = 0;
while (!pq.isEmpty()) {
const [effort, row, col] = pq.dequeue().element;
if (effort > efforts[row][col]) continue;
if (row === rows - 1 && col === cols - 1) return effort;
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
const newEffort = Math.max(effort, Math.abs(heights[newRow][newCol] - heights[row][col]));
if (newEffort < efforts[newRow][newCol]) {
efforts[newRow][newCol] = newEffort;
pq.enqueue([newEffort, newRow, newCol], newEffort);
}
}
}
}
return -1;
}Time Complexity: O((V + E) log V) where V = rows * cols | Space Complexity: O(V)
4. Reachable Nodes With Restrictions
LeetCode 2368 | Difficulty: Medium | Acceptance: 43.9%
Problem: There is an undirected tree with n nodes labeled from 0 to n-1 and n-1 edges. You are given a 2D integer array edges of length n-1, where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an integer array restricted which contains a subset of nodes that are restricted and cannot be visited. Return the maximum number of nodes you can reach from node 0 without visiting a restricted node.
BFS for Tree Traversal: Use BFS to explore reachable nodes while respecting restrictions.
Solution Template:
function reachableNodes(n, edges, restricted) {
// Build adjacency list
const graph = Array.from({length: n}, () => []);
for (const [a, b] of edges) {
graph[a].push(b);
graph[b].push(a);
}
// Mark restricted nodes
const isRestricted = new Set(restricted);
// BFS to count reachable nodes
const queue = [0];
const visited = new Set([0]);
let count = 1;
while (queue.length > 0) {
const node = queue.shift();
for (const neighbor of graph[node]) {
if (!visited.has(neighbor) && !isRestricted.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
count++;
}
}
}
return count;
}Time Complexity: O(V + E) | Space Complexity: O(V + E)
5. Minimum Cost to Make at Least One Valid Path in a Grid
LeetCode 1368 | Difficulty: Hard | Acceptance: 66.7%
Problem: Given an m x n grid. Each cell of the grid has a sign pointing to the next cell you should visit if you are currently in this cell. The sign of grid[i][j] can be:
- 1 which means go to the right cell, i.e., go to (i, j + 1)
- 2 which means go to the left cell, i.e., go to (i, j - 1)
- 3 which means go to the lower cell, i.e., go to (i + 1, j)
- 4 which means go to the upper cell, i.e., go to (i - 1, j)
You can modify the sign on a cell with cost of 1. You need to make at least one valid path from the top-left cell (0,0) to the bottom-right cell (m-1, n-1). Return the minimum cost.
BFS with State Modification: Use BFS where state includes position and cost, treating each cell as a possible change point.
Solution Template:
function minCost(grid) {
const rows = grid.length;
const cols = grid[0].length;
const directions = [
[0, 1], [0, -1], [1, 0], [-1, 0] // right, left, down, up
];
// Queue: [row, col, cost]
const queue = [[0, 0, 0]];
const visited = Array.from({length: rows}, () => new Array(cols).fill(Infinity));
visited[0][0] = 0;
while (queue.length > 0) {
const [row, col, cost] = queue.shift();
if (row === rows - 1 && col === cols - 1) return cost;
// Try all directions from current cell
for (let d = 0; d < 4; d++) {
const newRow = row + directions[d][0];
const newCol = col + directions[d][1];
if (newRow >= 0 && newRow < rows && newCol >= 0 && newCol < cols) {
// Calculate cost: 0 if direction matches sign, 1 if not
const signCost = (grid[row][col] === d + 1) ? 0 : 1;
const newCost = cost + signCost;
if (newCost < visited[newRow][newCol]) {
visited[newRow][newCol] = newCost;
// Use binary insertion to maintain cost order (0-1 BFS alternative)
queue.push([newRow, newCol, newCost]);
queue.sort((a, b) => a[2] - b[2]); // Sort by cost
}
}
}
}
return -1;
}Time Complexity: O((V + E) log V) due to sorting | Space Complexity: O(V)
Hard Problems
6. Swim in Rising Water
LeetCode 778 | Difficulty: Hard | Acceptance: 59.6%
Problem: On an N x N grid, each square grid[x][y] represents the elevation at that point (x, y). From the top left square (0, 0), you can move to adjacent squares (up, down, left, right) if their elevations are at most the current water level. As the water rises, more squares become accessible. Write a function that returns the least time until you can reach the bottom right square (N-1, N-1) from the top left square (0, 0).
Binary Search + DFS/BFS: Use binary search on water level, check connectivity with DFS/BFS.
Solution Template:
function swimInWater(grid) {
const n = grid.length;
let left = grid[0][0];
let right = n * n - 1;
while (left < right) {
const mid = Math.floor((left + right) / 2);
if (canReachEnd(grid, mid)) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
function canReachEnd(grid, waterLevel) {
const n = grid.length;
const visited = Array.from({length: n}, () => new Array(n).fill(false));
const queue = [[0, 0]];
visited[0][0] = true;
const directions = [[0, 1], [1, 0], [0, -1], [-1, 0]];
while (queue.length > 0) {
const [row, col] = queue.shift();
if (row === n - 1 && col === n - 1) return true;
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n &&
!visited[newRow][newCol] && grid[newRow][newCol] <= waterLevel) {
visited[newRow][newCol] = true;
queue.push([newRow, newCol]);
}
}
}
return false;
}Time Complexity: O(N² log N) | Space Complexity: O(N²)
7. Find the City With the Smallest Number of Neighbors at a Threshold Distance
LeetCode 1334 | Difficulty: Medium | Acceptance: 45.8%
Problem: There are n cities numbered from 0 to n-1. Given a 2D array edges where edges[i] = [fromi, toi, weighti] represents a bidirectional and weighted edge between cities fromi and toi, and given an integer distanceThreshold. Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold. If there are multiple such cities, return the city with the greatest number.
Floyd-Warshall for All-Pairs: Use Floyd-Warshall to compute all-pairs shortest paths, then analyze each city’s reachability.
Solution Template:
function findTheCity(n, edges, distanceThreshold) {
// Initialize distance matrix
const dist = Array.from({length: n}, () => new Array(n).fill(Infinity));
for (let i = 0; i < n; i++) {
dist[i][i] = 0;
}
for (const [from, to, weight] of edges) {
dist[from][to] = weight;
dist[to][from] = weight;
}
// Floyd-Warshall algorithm
for (let k = 0; k < n; k++) {
for (let i = 0; i < n; i++) {
for (let j = 0; j < n; j++) {
if (dist[i][k] !== Infinity && dist[k][j] !== Infinity) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
}
let minNeighbors = Infinity;
let resultCity = -1;
for (let i = 0; i < n; i++) {
let neighborCount = 0;
for (let j = 0; j < n; j++) {
if (dist[i][j] <= distanceThreshold && i !== j) {
neighborCount++;
}
}
if (neighborCount <= minNeighbors) {
if (neighborCount < minNeighbors || i > resultCity) {
minNeighbors = neighborCount;
resultCity = i;
}
}
}
return resultCity;
}Time Complexity: O(N³) | Space Complexity: O(N²)
8. Minimum Time to Visit All Points
LeetCode 1266 | Difficulty: Easy | Acceptance: 79.1%
Problem: On a 2D plane, there are n points with integer coordinates points[i] = [xi, yi]. Return the minimum time in seconds to visit all the points in the order given by points. You can move to any adjacent point (up, down, left, right) in 1 second, or to any diagonal point in 1 second (moving diagonally is allowed).
Chebyshev Distance: The minimum time between two points is the maximum of horizontal and vertical distance.
Solution Template:
function minTimeToVisitAllPoints(points) {
let totalTime = 0;
for (let i = 1; i < points.length; i++) {
const [x1, y1] = points[i - 1];
const [x2, y2] = points[i];
const dx = Math.abs(x2 - x1);
const dy = Math.abs(y2 - y1);
// Chebyshev distance: max(dx, dy)
totalTime += Math.max(dx, dy);
}
return totalTime;
}Time Complexity: O(n) | Space Complexity: O(1)
9. All Paths from Source to Target
LeetCode 797 | Difficulty: Medium | Acceptance: 82.4%
Problem: Given a directed acyclic graph (DAG) of n nodes labeled from 0 to n-1, find all possible paths from node 0 to node n-1, and return them in any order. The graph is given as follows: graph[i] is a list of all nodes you can visit from node i (i.e., there is a directed edge from node i to node graph[i][j]).
Backtracking with Paths: Use recursion to explore all paths, building path list along the way.
Solution Template:
function allPathsSourceTarget(graph) {
const result = [];
const path = [0];
function dfs(node) {
if (node === graph.length - 1) {
result.push([...path]);
return;
}
for (const neighbor of graph[node]) {
path.push(neighbor);
dfs(neighbor);
path.pop(); // Backtrack
}
}
dfs(0);
return result;
}Time Complexity: O(2^V) worst case, better for DAGs | Space Complexity: O(V) for recursion, O(V * paths) for result
10. Shortest Path in Binary Matrix
LeetCode 1091 | Difficulty: Medium | Acceptance: 44.6%
Problem: Given an n x n binary matrix grid, return the length of the shortest clear path in the matrix. If there is no clear path, return -1. A clear path in a binary matrix is a path from the top-left cell (i.e., (0, 0)) to the bottom-right cell (i.e., (n - 1, n - 1)) such that:
- All the visited cells of the path are 0.
- All the adjacent cells of the path are 8-directionally connected (i.e., they are different and also connected whether or not they share an edge/ corner).
- The length of a clear path is the number of visited cells of this path.
BFS with Diagonal Movement: Use BFS allowing 8-directional movement, return path length.
Solution Template:
function shortestPathBinaryMatrix(grid) {
const n = grid.length;
if (grid[0][0] === 1 || grid[n-1][n-1] === 1) return -1;
const directions = [
[-1, -1], [-1, 0], [-1, 1],
[0, -1], [0, 1],
[1, -1], [1, 0], [1, 1]
];
const queue = [[0, 0, 1]]; // [row, col, distance]
const visited = Array.from({length: n}, () => new Array(n).fill(false));
visited[0][0] = true;
while (queue.length > 0) {
const [row, col, dist] = queue.shift();
if (row === n - 1 && col === n - 1) return dist;
for (const [dr, dc] of directions) {
const newRow = row + dr;
const newCol = col + dc;
if (newRow >= 0 && newRow < n && newCol >= 0 && newCol < n &&
grid[newRow][newCol] === 0 && !visited[newRow][newCol]) {
visited[newRow][newCol] = true;
queue.push([newRow, newCol, dist + 1]);
}
}
}
return -1;
}Time Complexity: O(n²) | Space Complexity: O(n²)
Practice Strategy
1. Start with BFS Fundamentals
- Practice grid-based shortest paths
- Understand 4-way vs 8-way movement
- Master visited array management
2. Move to Dijkstra
- Implement priority queue versions
- Practice with different graph representations
- Solve network delay and routing problems
3. Study Floyd-Warshall
- Understand all-pairs computation
- Practice with small graphs first
- Solve connectivity problems
4. Apply Advanced Techniques
- Binary search + BFS for threshold problems
- Multi-constraint pathfinding
- Real-world applications like navigation
5. Optimize and Compare
- Analyze algorithm trade-offs
- Implement different approaches
- Identify best solution for constraints
Common Patterns to Recognize
- Grid BFS → Distance-based exploration
- Network routing → Dijkstra with priority queues
- All-pairs shortest paths → Floyd-Warshall for dense graphs
- Minimum spanning tree → Prim’s/Dijkstra connection
- Negative weights → Bellman-Ford requirement
- Heuristic guidance → A* for goal-directed search
Interview Tips
- Algorithm selection: Choose based on graph weights and connectivity
- Graph representation: Adjacency list for sparse, matrix for dense
- Priority queues: Critical for Dijkstra performance
- Visited arrays: Essential in grid BFS to prevent cycles
- Edge cases: Source/target both obstacles, disconnected graphs
- Time complexity: Trade-offs between V+E*logV and V³
- Implementation details: Decrease-key operations, negative cycles
Common Mistakes
- Wrong graph type: Using Dijkstra on negative weight graphs
- Visited placement: Marking visited before vs after enqueue
- Priority queue updates: Not properly updating existing entries
- Infinite loops: Forgetting visited checks in BFS
- Matrix bounds: Off-by-one errors in grid problems
- Unreachable nodes: Not handling disconnected graphs
Ready for more practice? Check out our code templates for reusable shortest path implementations.