A* Search in Coding Interviews: When Dijkstra Is Not Enough
Linkjob AIA* rarely appears as a named LeetCode problem, but it is a great answer to grid shortest-path follow-ups such as 'the grid is huge, can you do better than BFS?'.
The idea
Dijkstra expands nodes in order of g(n), the cost so far. A* expands in order of f(n) = g(n) + h(n), where h(n) estimates the remaining cost. A good heuristic steers the search toward the goal so far fewer nodes are expanded.
Admissible and consistent heuristics
If h never overestimates (admissible), A* returns an optimal path. If h also satisfies h(u) <= cost(u, v) + h(v) (consistent), each node is settled once, like Dijkstra. On a 4-direction grid with unit costs, Manhattan distance is both. With diagonal moves use Chebyshev or octile distance.
Code (Python, grid with walls)
import heapq
def astar(grid, start, goal):
h = lambda p: abs(p[0]-goal[0]) + abs(p[1]-goal[1])
best = {start: 0}
pq = [(h(start), 0, start)]
while pq:
f, g, (r, c) = heapq.heappop(pq)
if (r, c) == goal: return g
if g > best[(r, c)]: continue
for nr, nc in ((r+1,c),(r-1,c),(r,c+1),(r,c-1)):
if 0 <= nr < len(grid) and 0 <= nc < len(grid[0]) and grid[nr][nc] == 0:
ng = g + 1
if ng < best.get((nr, nc), float('inf')):
best[(nr, nc)] = ng
heapq.heappush(pq, (ng + h((nr, nc)), ng, (nr, nc)))
return -1Trade-offs to mention
With h = 0, A* is Dijkstra. On an unweighted grid with no obstacles plain BFS is already optimal and simpler, so say when A* is worth the extra code: large or weighted maps with a meaningful heuristic. Memory, not time, is often the limit, which leads to IDA* as a follow-up.
I help build Linkjob AI, a coding interview copilot that suggests follow-up angles like this one in real time; you can try it free.