Shortest Path In Grid — Problem Statement & Solution Guide
Problem Description
Given a grid of nodes represented as a list of node connections, find the shortest path to the central node. The grid is a list of pairs, where each pair represents a connection between two nodes. The central node is the node at the middle index of the sorted list of all nodes in the grid.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Shortest Path In Grid"
WHY DOES IT MATTER?
Shortest‑path‑in‑unweighted‑graph is a foundational pattern that appears in routing, social‑network analysis, and game AI. Mastering BFS for this pattern equips engineers to solve any problem where the cost metric is uniform and the goal is minimal hops.
OPTIMIZATION CHALLENGE
The key insight is to treat the central node as the BFS source instead of running a separate search from every other node. This single traversal simultaneously yields the shortest distance to all nodes, collapsing what could be O(V·(V+E)) work into O(V+E).
REAL-WORLD CONNECTION
Think of a city’s subway system where each station is a node and each direct line is an edge. Finding the fewest stops from any station to the central hub mirrors this problem, and BFS is exactly how transit apps compute optimal routes in real time.
During an interview, build the adjacency list first, sort the unique node IDs to locate the median, then launch BFS. Keep a visited set and a distance map; early exit is possible if you only need the distance for a specific start node.
COMPLEXITY AT A GLANCE
O(V + E)O(V + E)Core Theory — Why This Approach?
The problem reduces to finding the shortest unweighted path in an undirected graph. Each node is a vertex and each pair in the input list is an edge. Because all edges have equal weight, Breadth‑First Search (BFS) from the target (the central node) yields the minimum number of hops to every reachable vertex. Naïve approaches such as depth‑first search or exhaustive enumeration of all possible paths explode combinatorially: for a graph with V vertices and E edges, the number of simple paths can be exponential, making DFS impractical for large inputs. BFS, on the other hand, explores vertices level by level, guaranteeing that the first time a node is visited we have discovered the shortest path to it. The optimal paradigm therefore combines preprocessing (sorting all distinct node identifiers to locate the median) with a single BFS traversal, achieving linear time relative to the size of the graph.
Interview Questions on This Problem
Q1How would you modify the solution if edges had non‑uniform positive weights?
Replace BFS with Dijkstra's algorithm using a min‑heap priority queue. Initialize distances with infinity, set the central node distance to zero, and relax edges according to their weights. The algorithm runs in O((V+E) log V) time.
Q2What is the time‑space trade‑off when you need to answer multiple queries for shortest paths to different central nodes?
Pre‑compute all‑pairs shortest paths using Floyd‑Warshall (O(V^3) time, O(V^2) space) for small dense graphs, or build a series of BFS trees rooted at each possible central node on demand, caching results to reuse across queries, which keeps per‑query time O(V+E) but uses O(V) extra space per cached root.
Q3Explain how you would detect if the central node is isolated and what your algorithm should return in that case.
After sorting nodes to find the median, check its adjacency list. If it has no neighbors, BFS will only visit the central node itself. All other nodes remain at distance infinity (or -1). The algorithm should return a special marker (e.g., -1) for unreachable nodes, indicating the central node is isolated.
Examples
Input
[[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]]
Output
[0, 1, 2, 3]
Explanation: Step-by-step: with input [[0, 1], [1, 2], [2, 3], [3, 4], [4, 0]], we first identify the central node as 2. Then, we use a shortest path algorithm (such as BFS) to find the shortest path from node 0 to node 2, which is [0, 1, 2]. Then, we use the same algorithm to find the shortest path from node 2 to node 3, which is [2, 3]. Combining these two paths, we get [0, 1, 2, 3].
Input
[[0, 1], [1, 2], [2, 0], [0, 3], [3, 4]]
Output
[0, 3]
Explanation: Step-by-step: with input [[0, 1], [1, 2], [2, 0], [0, 3], [3, 4]], we first identify the central node as 2. However, since the grid is not a list of nodes, we need to first construct the graph. Then, we use a shortest path algorithm (such as BFS) to find the shortest path from node 0 to node 3, which is [0, 3].
Constraints
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9
Optimal Approach & Strategy
Run a single BFS starting at the central node; the first time a node is visited its distance is optimal.
Brute Force Approach
Enumerate every possible path from each node to the central node using depth‑first search and keep the shortest length found.
Verified Code Solutions
function solution(grid) {
// Create an adjacency list to represent the graph
const graph = {};
for (const [u, v] of grid) {
if (!graph[u]) graph[u] = [];
if (!graph[v]) graph[v] = [];
graph[u].push(v);
graph[v].push(u);
}
// Identify the central node
const centralNode = Math.floor(Object.keys(graph).length / 2);
// Use BFS to find the shortest path
const queue = [[0]];
const visited = new Set();
while (queue.length > 0) {
const path = queue.shift();
const node = path[path.length - 1];
if (node === centralNode) return path;
if (visited.has(node)) continue;
visited.add(node);
for (const neighbor of graph[node]) {
queue.push([...path, neighbor]);
}
}
return null;
}class Solution {
public:
vector<int> solution(vector<vector<int>>& grid) {
// Create an adjacency list to represent the graph
unordered_map<int, vector<int>> graph;
for (const auto& edge : grid) {
int u = edge[0];
int v = edge[1];
graph[u].push_back(v);
graph[v].push_back(u);
}
// Identify the central node
int centralNode = graph.size() / 2;
// Use BFS to find the shortest path
queue<vector<int>> q;
q.push({0});
unordered_set<int> visited;
while (!q.empty()) {
vector<int> path = q.front();
q.pop();
int node = path.back();
if (node == centralNode) return path;
if (visited.count(node)) continue;
visited.insert(node);
for (int neighbor : graph[node]) {
vector<int> newPath = path;
newPath.push_back(neighbor);
q.push(newPath);
}
}
return {};
}
};import java.util.*;
class Solution {
public int[] solution(int[][] grid) {
// Create an adjacency list to represent the graph
Map<Integer, List<Integer>> graph = new HashMap<>();
for (int[] edge : grid) {
int u = edge[0];
int v = edge[1];
graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
}
// Identify the central node
int centralNode = graph.size() / 2;
// Use BFS to find the shortest path
Queue<List<Integer>> queue = new LinkedList<>();
queue.offer(Collections.singletonList(0));
Set<Integer> visited = new HashSet<>();
while (!queue.isEmpty()) {
List<Integer> path = queue.poll();
int node = path.get(path.size() - 1);
if (node == centralNode) return path.stream().mapToInt(i -> i).toArray();
if (visited.contains(node)) continue;
visited.add(node);
for (int neighbor : graph.get(node)) {
List<Integer> newPath = new ArrayList<>(path);
newPath.add(neighbor);
queue.offer(newPath);
}
}
return null;
}
}def solution(grid):
# Create an adjacency list to represent the graph
graph = {}
for u, v in grid:
if u not in graph: graph[u] = []
if v not in graph: graph[v] = []
graph[u].append(v)
graph[v].append(u)
# Identify the central node
central_node = len(graph) // 2
# Use BFS to find the shortest path
queue = [[0]]
visited = set()
while queue:
path = queue.pop(0)
node = path[-1]
if node == central_node: return path
if node in visited: continue
visited.add(node)
for neighbor in graph[node]:
queue.append(path + [neighbor])
return Nonefunction solution(grid) {
// Create an adjacency list to represent the graph
const graph = {};
for (const [u, v] of grid) {
if (!graph[u]) graph[u] = [];
if (!graph[v]) graph[v] = [];
graph[u].push(v);
graph[v].push(u);
}
// Identify the central node
const centralNode = Math.floor(Object.keys(graph).length / 2);
// Use BFS to find the shortest path
const queue = [[0]];
const visited = new Set();
while (queue.length > 0) {
const path = queue.shift();
const node = path[path.length - 1];
if (node === centralNode) return path;
if (visited.has(node)) continue;
visited.add(node);
for (const neighbor of graph[node]) {
queue.push([...path, neighbor]);
}
}
return null;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.