What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Graph Algorithms

Builds on Dijkstra, which you haven’t finished yet.

P3MediumBuilt on Dijkstra~6 min speedrun

A* Search (Cost So Far Plus a Guess)

Built on

DijkstraThe heap orders states by the cost so far plus a guess of the cost still to go, and the guess must never be too large.

The problem

Shortest Path in Binary Matrix (LC 1091)(opens leetcode.com)

You get a square grid grid with n rows and n columns. Each cell holds 0 or 1. A cell with 0 is open. A cell with 1 is blocked.

You start in the top-left cell (0, 0) and want to reach the bottom-right cell (n - 1, n - 1). In one move, you step to any of the 8 cells around you: up, down, left, right, or one of the 4 diagonals. You may stand only on open cells.

The length of a path is the number of cells on it, and the start cell counts. Return the length of the shortest path. Return -1 when no path exists.

Example 1

Input:grid = [[0,1],[1,0]]

Output:2

Step diagonally from (0, 0) to (1, 1). The path has 2 cells.

A Star Search

start + goal + a guess of the cost left ➔ min-heap (cost so far + guess) ➔ cheapest path to one goal

Spot it when: You need the cheapest path from one start to one goal, no step has a negative cost, and you can compute for any state a quick guess of the cost still to go that is never too large (rows and columns left on a grid, the sum of the tile distances in a sliding puzzle).

A Star Search

Python

1	import heapq
2	from typing import Callable, Hashable, Iterable, List, Tuple
3
4
5	def a_star(start: Hashable, is_goal: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Tuple[Hashable, int]]], guess: Callable[[Hashable], int]) -> int:
6	"""A* Search: the lowest total cost from start to a state where is_goal holds, or
7	-1.
8	neighbors(state) lists (next_state, step_cost) pairs.
9	Preconditions: every step_cost is 0 or more. guess(state) never returns more than
10	the true lowest cost from state to a goal, and guess(goal) is 0.
11	V = the states reached. T = the cost of one is_goal, neighbors or guess call
12	(neighbors lists at most T pairs).
13	Time: O(V * T * log(V * T)) \| Space: O(V * T) heap, O(V) best
14	"""
15	# best[state] = the lowest cost found so far from start to state
16	best = {start: 0}
17	# (cost so far + guess, cost so far, state)
18	pq = [(guess(start), 0, start)]
19
20	while pq:
21	# 1. Pop the Smallest Cost So Far Plus Guess, and Skip a Stale Entry:
22	# A state can wait in pq several times, once for each time its cost got lower.
23	# Only the entry whose cost equals best[state] is current.
24	_, cost, state = heapq.heappop(pq)
25	if cost > best[state]:
26	continue
27
28	# 2. Check for the Goal When It Is Popped, Not When It Is Pushed:
29	# With a guess that is never too large, no waiting entry can lead to a cheaper
30	# goal.
31	# A goal that was only pushed may still have a cheaper way in.
32	if is_goal(state):
33	return cost
34
35	# 3. Push Every Neighbour That Now Costs Less:
36	# The new entry is ordered by new_cost + guess(nxt), the lowest total cost that
37	# can still be reached through nxt.
38	for nxt, step in neighbors(state):
39	new_cost = cost + step
40	if new_cost < best.get(nxt, float("inf")):
41	best[nxt] = new_cost
42	heapq.heappush(pq, (new_cost + guess(nxt), new_cost, nxt))
43
44	return -1

Invariant: Every entry in pq is ordered by cost + guess(state), and guess never returns more than the true cost still to go, so when the goal is popped, every other path is still behind an entry that is at least as large.

Order pq by cost + guess(state), where cost is the lowest cost found so far from start to state and guess(state) is a quick estimate of the cost still to go. States that lead away from the goal get a large total and wait at the back of pq, so the search reaches the goal after fewer pops than Dijkstra's algorithm. The result is correct when guess never returns more than the true cost still to go, which is called an admissible guess, and when guess(goal) is 0. Then cost + guess of a waiting state is never more than the cost of the best path through that state. When the goal is popped, every other path to it is still behind a waiting state whose total is at least as large, so cost is the lowest. If guess is also consistent, which means guess(state) is never more than step + guess(nxt) for any step, the first pop of a state already has its final cost. With guess equal to 0 for every state, the code is Dijkstra's algorithm. The trap is a guess that can be too large. In Shortest Path in Binary Matrix (LC 1091), (n - 1 - r) + (n - 1 - c) counts a diagonal move twice, so it can be larger than the real number of moves left, and the search returns a longer path. Use max(n - 1 - r, n - 1 - c).

See it run

A* Search, step by step

pq (5,1,0,0)pops 0

Each cell of the grid is one cell of the board. # is a wall. A cell that was pushed shows its cost, a plus sign, then its guess. A blank cell has not been reached.

pop the cell taken from the heap, with the smallest cost plus guess
pushed a neighbour that now costs less and is pushed
waiting a cell with an entry in the heap that is not popped yet
done a cell that was popped and expanded
goal the bottom-right cell

Start: the start cell has cost 1 and guess 4, so it is pushed with total 5.

row 0

1+4waiting

row 1

row 2

row 3

row 4

1 / 11

Gotchas1 of 5

The trap
Gotcha 1: Using a guess that can be larger than the true cost still to go
Mistake
```
return (n - 1 - r) + (n - 1 - c)
```
Fix
```
return max(n - 1 - r, n - 1 - c)
```
What happens: guess must never return more than the number of cells still to be added to the path. A diagonal move changes the row and the column in one move. The sum of the rows left and the columns left counts such a move twice, so it can be larger than the real number of moves left. A cell on the shortest path then gets a total that is too large, and it waits behind cells of a longer path. The bottom-right cell is popped by the longer path first. In the example, the shortest path has 6 cells, and the search returns 7.
Example: grid = [[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
Mistake: returns 7Fix: returns 6
Gotcha 2: Skipping the stale check after the pop
Mistake
```
_, cost, state = heapq.heappop(pq)
```
Fix
```
_, cost, state = heapq.heappop(pq)
if cost > best[state]:
    continue
```
What happens: A state is pushed again each time its cost gets lower. So pq can hold an older entry for it with a higher cost. The lower entry has a smaller total, so it is popped first and its neighbours are already updated. Without the check, the older entry expands the state again. Every neighbour test fails, because the new cost is not lower than best. The answer stays right, but the run repeats work. That is why this mistake has no example.
Gotcha 3: Checking the goal when it is pushed instead of when it is popped
Mistake
```
for nxt, step in neighbors(state):
    new_cost = cost + step
    if is_goal(nxt):
        return new_cost
```
Fix
```
if is_goal(state):
    return cost
```
What happens: A pushed goal has a cost, but a cheaper way to the goal can still wait in pq. The test must run when the goal is popped, because then no waiting entry has a smaller total. In the example, S has two ways to G. The way through A costs 1 + 10 = 11 and the way through B costs 2 + 2 = 4. The goal is first pushed from A, with cost 11. The version that returns at the push gives 11, and the right answer is 4.
Example: edges S to A (1), S to B (2), A to G (10), B to G (2); start S, goal G, guess 0
Mistake: returns 11Fix: returns 4
Gotcha 4: Marking a state as seen the first time it is pushed
Mistake
```
if nxt not in seen:
    seen.add(nxt)
```
Fix
```
if new_cost < best.get(nxt, float("inf")):
    best[nxt] = new_cost
```
What happens: Breadth-first search marks a cell when it is first reached, because that way is already the shortest. Here the first way to a state can be the more expensive one. A later way with a lower cost must be allowed to replace it. With a seen set, the later way is thrown away. In the example, A is first reached from S with cost 5. The way through B costs 1 + 1 = 2, and it is ignored. The version with seen gives 6, and the right answer is 3.
Example: edges S to A (5), S to B (1), B to A (1), A to G (1); start S, goal G, guess 0
Mistake: returns 6Fix: returns 3
Gotcha 5: Ordering pq by the guess alone
Mistake
```
heapq.heappush(pq, (guess(nr, nc), cost + 1, nr, nc))
```
Fix
```
heapq.heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc))
```
What happens: A key of guess alone ignores the cost so far. The search always follows the cell that looks closest to the goal, even when the way to it was long. The first path that reaches the goal is returned, and it is not always the shortest. In the example, the shortest path has 5 cells. The search that orders by the guess alone returns 6.
Example: grid = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]
Mistake: returns 6Fix: returns 5

Not this one if…

You need the cheapest distance to every node, as in Network Delay Time (LC 743), so there is no single goal to aim at and no guess can help: use Dijkstra's algorithm. See Dijkstra
Every move costs the same and the goal is not one known cell, as in Nearest Exit from Entrance in Maze (LC 1926), where any border cell is an exit: there is no position to measure toward, so a plain queue is enough. See Shortest-Path BFS
The route may use at most k stops, as in Cheapest Flights Within K Stops (LC 787), and the cities give no position that could serve as a guess: use the rounds of Bellman-Ford. See Bellman-Ford

Deep Dive

Why the first pop of the goal is the cheapest path

pq holds entries (cost + guess, cost, state). A pop returns the entry with the smallest cost + guess. This is the pop of Dijkstra's algorithm, with guess added to the order.

A guess is admissible when guess(state) is never more than the true lowest cost from state to the goal, and guess(goal) is 0. Here is why the first popped goal has the lowest cost.

Suppose the goal is popped with cost = C, and a path to the goal with a lower cost C' exists. Take that path. Before the goal is popped, one state x on it waits in pq with the cost it has on that path. The total of that entry is the cost up to x plus guess(x). The guess is at most the cost of the rest of the path, so the total is at most C'. The goal entry has the total C, which is larger than C'. But pq returned the goal entry as the smallest. This is a contradiction, so no cheaper path exists.

A guess is consistent when guess(state) is never more than step + guess(nxt) for every move. Then cost + guess never drops along a path, and the first pop of a state already has its final cost. A consistent guess is also admissible. The guess max(n - 1 - r, n - 1 - c) is consistent, because one move changes it by at most 1 and every move costs 1.

Example: in Shortest Path in Binary Matrix (LC 1091), the grid [[0,0,0],[1,1,0],[1,1,0]] pops (0, 0), (0, 1), (1, 2) and (2, 2). The cell (0, 2) is pushed with total 5 and is never popped. The answer is 4.

One trace: the goal is pushed, then popped

The board runs shortestPathBinaryMatrix on a 5 by 5 grid with three walls. A cell that was pushed shows its cost, a plus sign and its guess. The start cell has cost 1 and guess 4, so its total is 5.

Every pop after the first one has the total 6. Cells with a larger total wait and are never popped: (2, 0) has total 7, and (0, 3) has total 8. In all, 19 of the 22 open cells are pushed, and only 10 are popped.

The goal (4, 4) is pushed when (3, 3) is popped, with cost 6 and total 6. The code does not stop there. The cell (4, 3) has the same total and a lower cost, so it is popped first. Then (4, 4) is popped, and the code returns 6.

That is the step marked as the trap on the board. A goal that is only pushed may still have a cheaper way in. On this grid the early check would give the same answer, but with different step costs it returns a longer path, as the third gotcha of the card shows.

A guess that is too large, and a guess of zero

The same grid shows what a bad guess does. Take the sum of the rows left and the columns left. At (0, 1) the sum is 4 + 3 = 7. The path from (0, 1) to the goal needs only 4 more cells, so the guess is 3 too large.

Entries on the real shortest path then look too expensive. The search pops (0, 0), (0, 1), (1, 2), (1, 3), (2, 4), (3, 4) and (4, 4), and returns 7. The shortest path has 6 cells.

Now take guess equal to 0 for every state. Every entry has the total cost, and the code is Dijkstra's algorithm. It pops all 22 open cells and returns 6, the same answer as the card's guess. A guess of 0 is never too large, so it is always safe. It only gives up the saving: the card's guess pops 10 cells.

So the guess does not decide whether the answer is right, as long as it is not too large. It decides how many cells are popped. A guess that is too large breaks the answer. A guess of 0 keeps the answer and pops the most cells.

The cost, and where a guess comes from

The worst case is the same as for Dijkstra's algorithm. Each cell is expanded once, because the guess is consistent. Each expansion pushes at most 8 entries. Each push and pop costs O(log N). The total is O(N^2 log N) time and O(N^2) space for an N by N grid.

The saving is in the number of pops. On an empty N by N grid, only the N cells on the diagonal are popped, and a guess of 0 pops all N^2 cells.

A good guess often comes from an easier version of the problem. Ignore the walls, and the fewest moves from a cell is max(rows left, columns left). Ignore the other tiles of a Sliding Puzzle (LC 773), and every tile needs at least its row distance plus its column distance. The sum of those distances is the guess. On Example 3, [[4,1,2],[5,0,3]], this guess pops 6 boards and a guess of 0 pops 19. The answer is 5 in both cases.

In Minimum Moves to Move a Box to Their Target Location (LC 1263), each push moves the box one cell, so the distance from the box to the target is a guess that is never too large. Walking is free, so only pushes count in cost.

Use Dijkstra's algorithm (the cheapest-first card) when you need the distance to every node, because there is then no single goal to aim at. Use Shortest-Path BFS (the fewest-steps card) when every move costs the same and no guess helps. Use Bellman-Ford (the relax-k-times card) when the number of edges is capped.

60-Second Pitch

"There is one start and one known goal, and no step is negative, so I use A star search. It is Dijkstra's algorithm with a different heap order. I order the heap by the cost so far plus a guess of the cost still to go. For the grid, the guess is the larger of the rows left and the columns left. It is never too large, because a diagonal move lowers both numbers at once. I keep best for the lowest cost of each cell and skip a stale entry. I check the goal when it is popped, not when it is pushed. Then every other path is still behind an entry with a total at least as large, so the cost is the lowest. The worst case is the same as Dijkstra's, order N squared times log N. The guess only lowers the number of pops. If the guess were too large, the answer could be longer than the best path."

Common Questions

What is the difference between an admissible and a consistent guess?: An admissible guess is never more than the true cost still to go. A consistent guess is never more than step + guess(nxt) for every move. A consistent guess is also admissible. With a consistent guess, the first pop of a state is final. With an admissible guess only, a state can be popped again with a lower cost, and the best check handles that.
What happens when the guess is too large?: The search can return a path that is longer than the best one. On the 5 by 5 grid of the first gotcha, rows left plus columns left returns 7 cells, and the best path has 6.
Is A* faster than Dijkstra's algorithm?: Not in the worst case. Both are O(N^2 log N) on the grid. A* usually pops fewer states, because the guess keeps states that lead away from the goal waiting. On an empty grid it pops N cells and Dijkstra's algorithm pops N^2.
How do you find a guess?: Solve an easier version of the problem. Remove the walls from the grid, or the other tiles from the puzzle. The cost of the easier version is never larger than the real cost, so it is a safe guess. Check that the guess is 0 at the goal.
What if the steps have different costs?: A* still works. Keep cost as the sum of the step costs, and give the guess in the same unit. Check the goal when it is popped. If a step is negative, use Bellman-Ford instead.

SWE Reasoning

Spot it

The question asks for the cheapest or shortest path from one start to one known goal.
No step has a negative cost. Say this out loud, because A* keeps Dijkstra's rule.
You can compute a quick guess of the cost still to go for any state, such as the rows and columns left on a grid, the tile distances of a puzzle, or the distance from a box to its target.
The guess comes from an easier version of the problem, so it is never larger than the real cost left.
A plain BFS or Dijkstra would work, but it pops many states that lead away from the goal.

The invariant, step by step

best[start] = 0 (or 1 when the path counts cells), and pq holds (guess(start), 0, start).
Each pop returns the entry with the smallest cost + guess.
If cost > best[state], a cheaper entry for the state was already handled. Skip this stale entry.
If the state is the goal, return cost. Every other path to the goal is still behind a waiting entry with a total at least as large, because guess is never too large.
For each neighbour, if cost + step is lower than best[nxt], store it and push (cost + step + guess(nxt), cost + step, nxt).
When pq is empty, the goal cannot be reached, so return -1.

Traps

A guess in the wrong unit. If a step costs 3, the guess must also be counted in units of 3. A guess in moves, used with costs in minutes, can be too large or too small.
A negative step cost. The proof above uses non-negative costs, as Dijkstra's algorithm does. A negative step breaks it.
Entries that tie. When two entries have the same cost + guess and the same cost, Python compares the next field. If the states are objects that cannot be compared, a TypeError is raised. Put a counter before the state, or use cells and strings that can be compared.
A guess that is not 0 at the goal. The proof needs guess(goal) = 0. Otherwise the total of the goal entry is larger than its cost.

Practice

Canonical LeetCode:Shortest Path in Binary Matrix (LC 1091)Sliding Puzzle (LC 773)Minimum Moves to Move a Box to Their Target Location (LC 1263)Shortest Path in a Grid with Obstacles Elimination (LC 1293)Open the Lock (LC 752)Minimum Knight Moves (LC 1197)

Theory Context•Graph Algorithms

Builds on Dijkstra, which you haven’t finished yet.

P3MediumBuilt on Dijkstra~6 min speedrun

A* Search (Cost So Far Plus a Guess)

Built on

DijkstraThe heap orders states by the cost so far plus a guess of the cost still to go, and the guess must never be too large.

The problem

Shortest Path in Binary Matrix (LC 1091)(opens leetcode.com)

You get a square grid grid with n rows and n columns. Each cell holds 0 or 1. A cell with 0 is open. A cell with 1 is blocked.

The length of a path is the number of cells on it, and the start cell counts. Return the length of the shortest path. Return -1 when no path exists.

Example 1

Input:grid = [[0,1],[1,0]]

Output:2

Step diagonally from (0, 0) to (1, 1). The path has 2 cells.

A Star Search

start + goal + a guess of the cost left ➔ min-heap (cost so far + guess) ➔ cheapest path to one goal

A Star Search

Python

1	import heapq
2	from typing import Callable, Hashable, Iterable, List, Tuple
3
4
5	def a_star(start: Hashable, is_goal: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Tuple[Hashable, int]]], guess: Callable[[Hashable], int]) -> int:
6	"""A* Search: the lowest total cost from start to a state where is_goal holds, or
7	-1.
8	neighbors(state) lists (next_state, step_cost) pairs.
9	Preconditions: every step_cost is 0 or more. guess(state) never returns more than
10	the true lowest cost from state to a goal, and guess(goal) is 0.
11	V = the states reached. T = the cost of one is_goal, neighbors or guess call
12	(neighbors lists at most T pairs).
13	Time: O(V * T * log(V * T)) \| Space: O(V * T) heap, O(V) best
14	"""
15	# best[state] = the lowest cost found so far from start to state
16	best = {start: 0}
17	# (cost so far + guess, cost so far, state)
18	pq = [(guess(start), 0, start)]
19
20	while pq:
21	# 1. Pop the Smallest Cost So Far Plus Guess, and Skip a Stale Entry:
22	# A state can wait in pq several times, once for each time its cost got lower.
23	# Only the entry whose cost equals best[state] is current.
24	_, cost, state = heapq.heappop(pq)
25	if cost > best[state]:
26	continue
27
28	# 2. Check for the Goal When It Is Popped, Not When It Is Pushed:
29	# With a guess that is never too large, no waiting entry can lead to a cheaper
30	# goal.
31	# A goal that was only pushed may still have a cheaper way in.
32	if is_goal(state):
33	return cost
34
35	# 3. Push Every Neighbour That Now Costs Less:
36	# The new entry is ordered by new_cost + guess(nxt), the lowest total cost that
37	# can still be reached through nxt.
38	for nxt, step in neighbors(state):
39	new_cost = cost + step
40	if new_cost < best.get(nxt, float("inf")):
41	best[nxt] = new_cost
42	heapq.heappush(pq, (new_cost + guess(nxt), new_cost, nxt))
43
44	return -1

See it run

A* Search, step by step

pq (5,1,0,0)pops 0

Each cell of the grid is one cell of the board. # is a wall. A cell that was pushed shows its cost, a plus sign, then its guess. A blank cell has not been reached.

pop the cell taken from the heap, with the smallest cost plus guess
pushed a neighbour that now costs less and is pushed
waiting a cell with an entry in the heap that is not popped yet
done a cell that was popped and expanded
goal the bottom-right cell

Start: the start cell has cost 1 and guess 4, so it is pushed with total 5.

row 0

1+4waiting

row 1

row 2

row 3

row 4

1 / 11

Gotchas1 of 5

The trap
Gotcha 1: Using a guess that can be larger than the true cost still to go
Mistake
```
return (n - 1 - r) + (n - 1 - c)
```
Fix
```
return max(n - 1 - r, n - 1 - c)
```
What happens: guess must never return more than the number of cells still to be added to the path. A diagonal move changes the row and the column in one move. The sum of the rows left and the columns left counts such a move twice, so it can be larger than the real number of moves left. A cell on the shortest path then gets a total that is too large, and it waits behind cells of a longer path. The bottom-right cell is popped by the longer path first. In the example, the shortest path has 6 cells, and the search returns 7.
Example: grid = [[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
Mistake: returns 7Fix: returns 6
Gotcha 2: Skipping the stale check after the pop
Mistake
```
_, cost, state = heapq.heappop(pq)
```
Fix
```
_, cost, state = heapq.heappop(pq)
if cost > best[state]:
    continue
```
What happens: A state is pushed again each time its cost gets lower. So pq can hold an older entry for it with a higher cost. The lower entry has a smaller total, so it is popped first and its neighbours are already updated. Without the check, the older entry expands the state again. Every neighbour test fails, because the new cost is not lower than best. The answer stays right, but the run repeats work. That is why this mistake has no example.
Gotcha 3: Checking the goal when it is pushed instead of when it is popped
Mistake
```
for nxt, step in neighbors(state):
    new_cost = cost + step
    if is_goal(nxt):
        return new_cost
```
Fix
```
if is_goal(state):
    return cost
```
What happens: A pushed goal has a cost, but a cheaper way to the goal can still wait in pq. The test must run when the goal is popped, because then no waiting entry has a smaller total. In the example, S has two ways to G. The way through A costs 1 + 10 = 11 and the way through B costs 2 + 2 = 4. The goal is first pushed from A, with cost 11. The version that returns at the push gives 11, and the right answer is 4.
Example: edges S to A (1), S to B (2), A to G (10), B to G (2); start S, goal G, guess 0
Mistake: returns 11Fix: returns 4
Gotcha 4: Marking a state as seen the first time it is pushed
Mistake
```
if nxt not in seen:
    seen.add(nxt)
```
Fix
```
if new_cost < best.get(nxt, float("inf")):
    best[nxt] = new_cost
```
What happens: Breadth-first search marks a cell when it is first reached, because that way is already the shortest. Here the first way to a state can be the more expensive one. A later way with a lower cost must be allowed to replace it. With a seen set, the later way is thrown away. In the example, A is first reached from S with cost 5. The way through B costs 1 + 1 = 2, and it is ignored. The version with seen gives 6, and the right answer is 3.
Example: edges S to A (5), S to B (1), B to A (1), A to G (1); start S, goal G, guess 0
Mistake: returns 6Fix: returns 3
Gotcha 5: Ordering pq by the guess alone
Mistake
```
heapq.heappush(pq, (guess(nr, nc), cost + 1, nr, nc))
```
Fix
```
heapq.heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc))
```
What happens: A key of guess alone ignores the cost so far. The search always follows the cell that looks closest to the goal, even when the way to it was long. The first path that reaches the goal is returned, and it is not always the shortest. In the example, the shortest path has 5 cells. The search that orders by the guess alone returns 6.
Example: grid = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]
Mistake: returns 6Fix: returns 5

Not this one if…

You need the cheapest distance to every node, as in Network Delay Time (LC 743), so there is no single goal to aim at and no guess can help: use Dijkstra's algorithm. See Dijkstra
Every move costs the same and the goal is not one known cell, as in Nearest Exit from Entrance in Maze (LC 1926), where any border cell is an exit: there is no position to measure toward, so a plain queue is enough. See Shortest-Path BFS
The route may use at most k stops, as in Cheapest Flights Within K Stops (LC 787), and the cities give no position that could serve as a guess: use the rounds of Bellman-Ford. See Bellman-Ford

Deep Dive

Why the first pop of the goal is the cheapest path

pq holds entries (cost + guess, cost, state). A pop returns the entry with the smallest cost + guess. This is the pop of Dijkstra's algorithm, with guess added to the order.

A guess is admissible when guess(state) is never more than the true lowest cost from state to the goal, and guess(goal) is 0. Here is why the first popped goal has the lowest cost.

One trace: the goal is pushed, then popped

A guess that is too large, and a guess of zero

Entries on the real shortest path then look too expensive. The search pops (0, 0), (0, 1), (1, 2), (1, 3), (2, 4), (3, 4) and (4, 4), and returns 7. The shortest path has 6 cells.

The cost, and where a guess comes from

The saving is in the number of pops. On an empty N by N grid, only the N cells on the diagonal are popped, and a guess of 0 pops all N^2 cells.

60-Second Pitch

Common Questions

What is the difference between an admissible and a consistent guess?: An admissible guess is never more than the true cost still to go. A consistent guess is never more than step + guess(nxt) for every move. A consistent guess is also admissible. With a consistent guess, the first pop of a state is final. With an admissible guess only, a state can be popped again with a lower cost, and the best check handles that.
What happens when the guess is too large?: The search can return a path that is longer than the best one. On the 5 by 5 grid of the first gotcha, rows left plus columns left returns 7 cells, and the best path has 6.
Is A* faster than Dijkstra's algorithm?: Not in the worst case. Both are O(N^2 log N) on the grid. A* usually pops fewer states, because the guess keeps states that lead away from the goal waiting. On an empty grid it pops N cells and Dijkstra's algorithm pops N^2.
How do you find a guess?: Solve an easier version of the problem. Remove the walls from the grid, or the other tiles from the puzzle. The cost of the easier version is never larger than the real cost, so it is a safe guess. Check that the guess is 0 at the goal.
What if the steps have different costs?: A* still works. Keep cost as the sum of the step costs, and give the guess in the same unit. Check the goal when it is popped. If a step is negative, use Bellman-Ford instead.

SWE Reasoning

Spot it

The question asks for the cheapest or shortest path from one start to one known goal.
No step has a negative cost. Say this out loud, because A* keeps Dijkstra's rule.
You can compute a quick guess of the cost still to go for any state, such as the rows and columns left on a grid, the tile distances of a puzzle, or the distance from a box to its target.
The guess comes from an easier version of the problem, so it is never larger than the real cost left.
A plain BFS or Dijkstra would work, but it pops many states that lead away from the goal.

The invariant, step by step

best[start] = 0 (or 1 when the path counts cells), and pq holds (guess(start), 0, start).
Each pop returns the entry with the smallest cost + guess.
If cost > best[state], a cheaper entry for the state was already handled. Skip this stale entry.
If the state is the goal, return cost. Every other path to the goal is still behind a waiting entry with a total at least as large, because guess is never too large.
For each neighbour, if cost + step is lower than best[nxt], store it and push (cost + step + guess(nxt), cost + step, nxt).
When pq is empty, the goal cannot be reached, so return -1.

Traps

A guess in the wrong unit. If a step costs 3, the guess must also be counted in units of 3. A guess in moves, used with costs in minutes, can be too large or too small.
A negative step cost. The proof above uses non-negative costs, as Dijkstra's algorithm does. A negative step breaks it.
Entries that tie. When two entries have the same cost + guess and the same cost, Python compares the next field. If the states are objects that cannot be compared, a TypeError is raised. Put a counter before the state, or use cells and strings that can be compared.
A guess that is not 0 at the goal. The proof needs guess(goal) = 0. Otherwise the total of the goal entry is larger than its cost.

Practice

Theory Context•Graph Algorithms

Builds on Dijkstra, which you haven’t finished yet.

P3MediumBuilt on Dijkstra~6 min speedrun

A* Search (Cost So Far Plus a Guess)

Built on

DijkstraThe heap orders states by the cost so far plus a guess of the cost still to go, and the guess must never be too large.

The problem

Shortest Path in Binary Matrix (LC 1091)(opens leetcode.com)

You get a square grid grid with n rows and n columns. Each cell holds 0 or 1. A cell with 0 is open. A cell with 1 is blocked.

The length of a path is the number of cells on it, and the start cell counts. Return the length of the shortest path. Return -1 when no path exists.

Example 1

Input:grid = [[0,1],[1,0]]

Output:2

Step diagonally from (0, 0) to (1, 1). The path has 2 cells.

A Star Search

start + goal + a guess of the cost left ➔ min-heap (cost so far + guess) ➔ cheapest path to one goal

A Star Search

Python

1	import heapq
2	from typing import Callable, Hashable, Iterable, List, Tuple
3
4
5	def a_star(start: Hashable, is_goal: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Tuple[Hashable, int]]], guess: Callable[[Hashable], int]) -> int:
6	"""A* Search: the lowest total cost from start to a state where is_goal holds, or
7	-1.
8	neighbors(state) lists (next_state, step_cost) pairs.
9	Preconditions: every step_cost is 0 or more. guess(state) never returns more than
10	the true lowest cost from state to a goal, and guess(goal) is 0.
11	V = the states reached. T = the cost of one is_goal, neighbors or guess call
12	(neighbors lists at most T pairs).
13	Time: O(V * T * log(V * T)) \| Space: O(V * T) heap, O(V) best
14	"""
15	# best[state] = the lowest cost found so far from start to state
16	best = {start: 0}
17	# (cost so far + guess, cost so far, state)
18	pq = [(guess(start), 0, start)]
19
20	while pq:
21	# 1. Pop the Smallest Cost So Far Plus Guess, and Skip a Stale Entry:
22	# A state can wait in pq several times, once for each time its cost got lower.
23	# Only the entry whose cost equals best[state] is current.
24	_, cost, state = heapq.heappop(pq)
25	if cost > best[state]:
26	continue
27
28	# 2. Check for the Goal When It Is Popped, Not When It Is Pushed:
29	# With a guess that is never too large, no waiting entry can lead to a cheaper
30	# goal.
31	# A goal that was only pushed may still have a cheaper way in.
32	if is_goal(state):
33	return cost
34
35	# 3. Push Every Neighbour That Now Costs Less:
36	# The new entry is ordered by new_cost + guess(nxt), the lowest total cost that
37	# can still be reached through nxt.
38	for nxt, step in neighbors(state):
39	new_cost = cost + step
40	if new_cost < best.get(nxt, float("inf")):
41	best[nxt] = new_cost
42	heapq.heappush(pq, (new_cost + guess(nxt), new_cost, nxt))
43
44	return -1

See it run

A* Search, step by step

pq (5,1,0,0)pops 0

Each cell of the grid is one cell of the board. # is a wall. A cell that was pushed shows its cost, a plus sign, then its guess. A blank cell has not been reached.

pop the cell taken from the heap, with the smallest cost plus guess
pushed a neighbour that now costs less and is pushed
waiting a cell with an entry in the heap that is not popped yet
done a cell that was popped and expanded
goal the bottom-right cell

Start: the start cell has cost 1 and guess 4, so it is pushed with total 5.

row 0

1+4waiting

row 1

row 2

row 3

row 4

1 / 11

Gotchas1 of 5

The trap
Gotcha 1: Using a guess that can be larger than the true cost still to go
Mistake
```
return (n - 1 - r) + (n - 1 - c)
```
Fix
```
return max(n - 1 - r, n - 1 - c)
```
What happens: guess must never return more than the number of cells still to be added to the path. A diagonal move changes the row and the column in one move. The sum of the rows left and the columns left counts such a move twice, so it can be larger than the real number of moves left. A cell on the shortest path then gets a total that is too large, and it waits behind cells of a longer path. The bottom-right cell is popped by the longer path first. In the example, the shortest path has 6 cells, and the search returns 7.
Example: grid = [[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
Mistake: returns 7Fix: returns 6
Gotcha 2: Skipping the stale check after the pop
Mistake
```
_, cost, state = heapq.heappop(pq)
```
Fix
```
_, cost, state = heapq.heappop(pq)
if cost > best[state]:
    continue
```
What happens: A state is pushed again each time its cost gets lower. So pq can hold an older entry for it with a higher cost. The lower entry has a smaller total, so it is popped first and its neighbours are already updated. Without the check, the older entry expands the state again. Every neighbour test fails, because the new cost is not lower than best. The answer stays right, but the run repeats work. That is why this mistake has no example.
Gotcha 3: Checking the goal when it is pushed instead of when it is popped
Mistake
```
for nxt, step in neighbors(state):
    new_cost = cost + step
    if is_goal(nxt):
        return new_cost
```
Fix
```
if is_goal(state):
    return cost
```
What happens: A pushed goal has a cost, but a cheaper way to the goal can still wait in pq. The test must run when the goal is popped, because then no waiting entry has a smaller total. In the example, S has two ways to G. The way through A costs 1 + 10 = 11 and the way through B costs 2 + 2 = 4. The goal is first pushed from A, with cost 11. The version that returns at the push gives 11, and the right answer is 4.
Example: edges S to A (1), S to B (2), A to G (10), B to G (2); start S, goal G, guess 0
Mistake: returns 11Fix: returns 4
Gotcha 4: Marking a state as seen the first time it is pushed
Mistake
```
if nxt not in seen:
    seen.add(nxt)
```
Fix
```
if new_cost < best.get(nxt, float("inf")):
    best[nxt] = new_cost
```
What happens: Breadth-first search marks a cell when it is first reached, because that way is already the shortest. Here the first way to a state can be the more expensive one. A later way with a lower cost must be allowed to replace it. With a seen set, the later way is thrown away. In the example, A is first reached from S with cost 5. The way through B costs 1 + 1 = 2, and it is ignored. The version with seen gives 6, and the right answer is 3.
Example: edges S to A (5), S to B (1), B to A (1), A to G (1); start S, goal G, guess 0
Mistake: returns 6Fix: returns 3
Gotcha 5: Ordering pq by the guess alone
Mistake
```
heapq.heappush(pq, (guess(nr, nc), cost + 1, nr, nc))
```
Fix
```
heapq.heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc))
```
What happens: A key of guess alone ignores the cost so far. The search always follows the cell that looks closest to the goal, even when the way to it was long. The first path that reaches the goal is returned, and it is not always the shortest. In the example, the shortest path has 5 cells. The search that orders by the guess alone returns 6.
Example: grid = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]
Mistake: returns 6Fix: returns 5

Not this one if…

You need the cheapest distance to every node, as in Network Delay Time (LC 743), so there is no single goal to aim at and no guess can help: use Dijkstra's algorithm. See Dijkstra
Every move costs the same and the goal is not one known cell, as in Nearest Exit from Entrance in Maze (LC 1926), where any border cell is an exit: there is no position to measure toward, so a plain queue is enough. See Shortest-Path BFS
The route may use at most k stops, as in Cheapest Flights Within K Stops (LC 787), and the cities give no position that could serve as a guess: use the rounds of Bellman-Ford. See Bellman-Ford

Deep Dive

Why the first pop of the goal is the cheapest path

pq holds entries (cost + guess, cost, state). A pop returns the entry with the smallest cost + guess. This is the pop of Dijkstra's algorithm, with guess added to the order.

A guess is admissible when guess(state) is never more than the true lowest cost from state to the goal, and guess(goal) is 0. Here is why the first popped goal has the lowest cost.

One trace: the goal is pushed, then popped

A guess that is too large, and a guess of zero

Entries on the real shortest path then look too expensive. The search pops (0, 0), (0, 1), (1, 2), (1, 3), (2, 4), (3, 4) and (4, 4), and returns 7. The shortest path has 6 cells.

The cost, and where a guess comes from

The saving is in the number of pops. On an empty N by N grid, only the N cells on the diagonal are popped, and a guess of 0 pops all N^2 cells.

60-Second Pitch

Common Questions

What is the difference between an admissible and a consistent guess?: An admissible guess is never more than the true cost still to go. A consistent guess is never more than step + guess(nxt) for every move. A consistent guess is also admissible. With a consistent guess, the first pop of a state is final. With an admissible guess only, a state can be popped again with a lower cost, and the best check handles that.
What happens when the guess is too large?: The search can return a path that is longer than the best one. On the 5 by 5 grid of the first gotcha, rows left plus columns left returns 7 cells, and the best path has 6.
Is A* faster than Dijkstra's algorithm?: Not in the worst case. Both are O(N^2 log N) on the grid. A* usually pops fewer states, because the guess keeps states that lead away from the goal waiting. On an empty grid it pops N cells and Dijkstra's algorithm pops N^2.
How do you find a guess?: Solve an easier version of the problem. Remove the walls from the grid, or the other tiles from the puzzle. The cost of the easier version is never larger than the real cost, so it is a safe guess. Check that the guess is 0 at the goal.
What if the steps have different costs?: A* still works. Keep cost as the sum of the step costs, and give the guess in the same unit. Check the goal when it is popped. If a step is negative, use Bellman-Ford instead.

SWE Reasoning

Spot it

The question asks for the cheapest or shortest path from one start to one known goal.
No step has a negative cost. Say this out loud, because A* keeps Dijkstra's rule.
You can compute a quick guess of the cost still to go for any state, such as the rows and columns left on a grid, the tile distances of a puzzle, or the distance from a box to its target.
The guess comes from an easier version of the problem, so it is never larger than the real cost left.
A plain BFS or Dijkstra would work, but it pops many states that lead away from the goal.

The invariant, step by step

best[start] = 0 (or 1 when the path counts cells), and pq holds (guess(start), 0, start).
Each pop returns the entry with the smallest cost + guess.
If cost > best[state], a cheaper entry for the state was already handled. Skip this stale entry.
If the state is the goal, return cost. Every other path to the goal is still behind a waiting entry with a total at least as large, because guess is never too large.
For each neighbour, if cost + step is lower than best[nxt], store it and push (cost + step + guess(nxt), cost + step, nxt).
When pq is empty, the goal cannot be reached, so return -1.

Traps

A guess in the wrong unit. If a step costs 3, the guess must also be counted in units of 3. A guess in moves, used with costs in minutes, can be too large or too small.
A negative step cost. The proof above uses non-negative costs, as Dijkstra's algorithm does. A negative step breaks it.
Entries that tie. When two entries have the same cost + guess and the same cost, Python compares the next field. If the states are objects that cannot be compared, a TypeError is raised. Put a counter before the state, or use cells and strings that can be compared.
A guess that is not 0 at the goal. The proof needs guess(goal) = 0. Otherwise the total of the goal entry is larger than its cost.

Practice

Theory Context•Graph Algorithms

Builds on Dijkstra, which you haven’t finished yet.

P3MediumBuilt on Dijkstra~6 min speedrun

A* Search (Cost So Far Plus a Guess)

Built on

DijkstraThe heap orders states by the cost so far plus a guess of the cost still to go, and the guess must never be too large.

The problem

Shortest Path in Binary Matrix (LC 1091)(opens leetcode.com)

You get a square grid grid with n rows and n columns. Each cell holds 0 or 1. A cell with 0 is open. A cell with 1 is blocked.

The length of a path is the number of cells on it, and the start cell counts. Return the length of the shortest path. Return -1 when no path exists.

Example 1

Input:grid = [[0,1],[1,0]]

Output:2

Step diagonally from (0, 0) to (1, 1). The path has 2 cells.

A Star Search

start + goal + a guess of the cost left ➔ min-heap (cost so far + guess) ➔ cheapest path to one goal

A Star Search

Python

1	import heapq
2	from typing import Callable, Hashable, Iterable, List, Tuple
3
4
5	def a_star(start: Hashable, is_goal: Callable[[Hashable], bool], neighbors: Callable[[Hashable], Iterable[Tuple[Hashable, int]]], guess: Callable[[Hashable], int]) -> int:
6	"""A* Search: the lowest total cost from start to a state where is_goal holds, or
7	-1.
8	neighbors(state) lists (next_state, step_cost) pairs.
9	Preconditions: every step_cost is 0 or more. guess(state) never returns more than
10	the true lowest cost from state to a goal, and guess(goal) is 0.
11	V = the states reached. T = the cost of one is_goal, neighbors or guess call
12	(neighbors lists at most T pairs).
13	Time: O(V * T * log(V * T)) \| Space: O(V * T) heap, O(V) best
14	"""
15	# best[state] = the lowest cost found so far from start to state
16	best = {start: 0}
17	# (cost so far + guess, cost so far, state)
18	pq = [(guess(start), 0, start)]
19
20	while pq:
21	# 1. Pop the Smallest Cost So Far Plus Guess, and Skip a Stale Entry:
22	# A state can wait in pq several times, once for each time its cost got lower.
23	# Only the entry whose cost equals best[state] is current.
24	_, cost, state = heapq.heappop(pq)
25	if cost > best[state]:
26	continue
27
28	# 2. Check for the Goal When It Is Popped, Not When It Is Pushed:
29	# With a guess that is never too large, no waiting entry can lead to a cheaper
30	# goal.
31	# A goal that was only pushed may still have a cheaper way in.
32	if is_goal(state):
33	return cost
34
35	# 3. Push Every Neighbour That Now Costs Less:
36	# The new entry is ordered by new_cost + guess(nxt), the lowest total cost that
37	# can still be reached through nxt.
38	for nxt, step in neighbors(state):
39	new_cost = cost + step
40	if new_cost < best.get(nxt, float("inf")):
41	best[nxt] = new_cost
42	heapq.heappush(pq, (new_cost + guess(nxt), new_cost, nxt))
43
44	return -1

See it run

A* Search, step by step

pq (5,1,0,0)pops 0

Each cell of the grid is one cell of the board. # is a wall. A cell that was pushed shows its cost, a plus sign, then its guess. A blank cell has not been reached.

pop the cell taken from the heap, with the smallest cost plus guess
pushed a neighbour that now costs less and is pushed
waiting a cell with an entry in the heap that is not popped yet
done a cell that was popped and expanded
goal the bottom-right cell

Start: the start cell has cost 1 and guess 4, so it is pushed with total 5.

row 0

1+4waiting

row 1

row 2

row 3

row 4

1 / 11

Gotchas1 of 5

The trap
Gotcha 1: Using a guess that can be larger than the true cost still to go
Mistake
```
return (n - 1 - r) + (n - 1 - c)
```
Fix
```
return max(n - 1 - r, n - 1 - c)
```
What happens: guess must never return more than the number of cells still to be added to the path. A diagonal move changes the row and the column in one move. The sum of the rows left and the columns left counts such a move twice, so it can be larger than the real number of moves left. A cell on the shortest path then gets a total that is too large, and it waits behind cells of a longer path. The bottom-right cell is popped by the longer path first. In the example, the shortest path has 6 cells, and the search returns 7.
Example: grid = [[0, 0, 1, 0, 0], [0, 1, 0, 0, 0], [0, 0, 0, 1, 0], [0, 0, 0, 0, 0], [0, 0, 0, 0, 0]]
Mistake: returns 7Fix: returns 6
Gotcha 2: Skipping the stale check after the pop
Mistake
```
_, cost, state = heapq.heappop(pq)
```
Fix
```
_, cost, state = heapq.heappop(pq)
if cost > best[state]:
    continue
```
What happens: A state is pushed again each time its cost gets lower. So pq can hold an older entry for it with a higher cost. The lower entry has a smaller total, so it is popped first and its neighbours are already updated. Without the check, the older entry expands the state again. Every neighbour test fails, because the new cost is not lower than best. The answer stays right, but the run repeats work. That is why this mistake has no example.
Gotcha 3: Checking the goal when it is pushed instead of when it is popped
Mistake
```
for nxt, step in neighbors(state):
    new_cost = cost + step
    if is_goal(nxt):
        return new_cost
```
Fix
```
if is_goal(state):
    return cost
```
What happens: A pushed goal has a cost, but a cheaper way to the goal can still wait in pq. The test must run when the goal is popped, because then no waiting entry has a smaller total. In the example, S has two ways to G. The way through A costs 1 + 10 = 11 and the way through B costs 2 + 2 = 4. The goal is first pushed from A, with cost 11. The version that returns at the push gives 11, and the right answer is 4.
Example: edges S to A (1), S to B (2), A to G (10), B to G (2); start S, goal G, guess 0
Mistake: returns 11Fix: returns 4
Gotcha 4: Marking a state as seen the first time it is pushed
Mistake
```
if nxt not in seen:
    seen.add(nxt)
```
Fix
```
if new_cost < best.get(nxt, float("inf")):
    best[nxt] = new_cost
```
What happens: Breadth-first search marks a cell when it is first reached, because that way is already the shortest. Here the first way to a state can be the more expensive one. A later way with a lower cost must be allowed to replace it. With a seen set, the later way is thrown away. In the example, A is first reached from S with cost 5. The way through B costs 1 + 1 = 2, and it is ignored. The version with seen gives 6, and the right answer is 3.
Example: edges S to A (5), S to B (1), B to A (1), A to G (1); start S, goal G, guess 0
Mistake: returns 6Fix: returns 3
Gotcha 5: Ordering pq by the guess alone
Mistake
```
heapq.heappush(pq, (guess(nr, nc), cost + 1, nr, nc))
```
Fix
```
heapq.heappush(pq, (cost + 1 + guess(nr, nc), cost + 1, nr, nc))
```
What happens: A key of guess alone ignores the cost so far. The search always follows the cell that looks closest to the goal, even when the way to it was long. The first path that reaches the goal is returned, and it is not always the shortest. In the example, the shortest path has 5 cells. The search that orders by the guess alone returns 6.
Example: grid = [[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 1, 1], [0, 0, 0, 0]]
Mistake: returns 6Fix: returns 5

Not this one if…

You need the cheapest distance to every node, as in Network Delay Time (LC 743), so there is no single goal to aim at and no guess can help: use Dijkstra's algorithm. See Dijkstra
Every move costs the same and the goal is not one known cell, as in Nearest Exit from Entrance in Maze (LC 1926), where any border cell is an exit: there is no position to measure toward, so a plain queue is enough. See Shortest-Path BFS
The route may use at most k stops, as in Cheapest Flights Within K Stops (LC 787), and the cities give no position that could serve as a guess: use the rounds of Bellman-Ford. See Bellman-Ford

Deep Dive

Why the first pop of the goal is the cheapest path

pq holds entries (cost + guess, cost, state). A pop returns the entry with the smallest cost + guess. This is the pop of Dijkstra's algorithm, with guess added to the order.

A guess is admissible when guess(state) is never more than the true lowest cost from state to the goal, and guess(goal) is 0. Here is why the first popped goal has the lowest cost.

One trace: the goal is pushed, then popped

A guess that is too large, and a guess of zero

Entries on the real shortest path then look too expensive. The search pops (0, 0), (0, 1), (1, 2), (1, 3), (2, 4), (3, 4) and (4, 4), and returns 7. The shortest path has 6 cells.

The cost, and where a guess comes from

The saving is in the number of pops. On an empty N by N grid, only the N cells on the diagonal are popped, and a guess of 0 pops all N^2 cells.

60-Second Pitch

Common Questions

What is the difference between an admissible and a consistent guess?: An admissible guess is never more than the true cost still to go. A consistent guess is never more than step + guess(nxt) for every move. A consistent guess is also admissible. With a consistent guess, the first pop of a state is final. With an admissible guess only, a state can be popped again with a lower cost, and the best check handles that.
What happens when the guess is too large?: The search can return a path that is longer than the best one. On the 5 by 5 grid of the first gotcha, rows left plus columns left returns 7 cells, and the best path has 6.
Is A* faster than Dijkstra's algorithm?: Not in the worst case. Both are O(N^2 log N) on the grid. A* usually pops fewer states, because the guess keeps states that lead away from the goal waiting. On an empty grid it pops N cells and Dijkstra's algorithm pops N^2.
How do you find a guess?: Solve an easier version of the problem. Remove the walls from the grid, or the other tiles from the puzzle. The cost of the easier version is never larger than the real cost, so it is a safe guess. Check that the guess is 0 at the goal.
What if the steps have different costs?: A* still works. Keep cost as the sum of the step costs, and give the guess in the same unit. Check the goal when it is popped. If a step is negative, use Bellman-Ford instead.

SWE Reasoning

Spot it

The question asks for the cheapest or shortest path from one start to one known goal.
No step has a negative cost. Say this out loud, because A* keeps Dijkstra's rule.
You can compute a quick guess of the cost still to go for any state, such as the rows and columns left on a grid, the tile distances of a puzzle, or the distance from a box to its target.
The guess comes from an easier version of the problem, so it is never larger than the real cost left.
A plain BFS or Dijkstra would work, but it pops many states that lead away from the goal.

The invariant, step by step

best[start] = 0 (or 1 when the path counts cells), and pq holds (guess(start), 0, start).
Each pop returns the entry with the smallest cost + guess.
If cost > best[state], a cheaper entry for the state was already handled. Skip this stale entry.
If the state is the goal, return cost. Every other path to the goal is still behind a waiting entry with a total at least as large, because guess is never too large.
For each neighbour, if cost + step is lower than best[nxt], store it and push (cost + step + guess(nxt), cost + step, nxt).
When pq is empty, the goal cannot be reached, so return -1.

Traps

A guess in the wrong unit. If a step costs 3, the guess must also be counted in units of 3. A guess in moves, used with costs in minutes, can be too large or too small.
A negative step cost. The proof above uses non-negative costs, as Dijkstra's algorithm does. A negative step breaks it.
Entries that tie. When two entries have the same cost + guess and the same cost, Python compares the next field. If the states are objects that cannot be compared, a TypeError is raised. Put a counter before the state, or use cells and strings that can be compared.
A guess that is not 0 at the goal. The proof needs guess(goal) = 0. Otherwise the total of the goal entry is larger than its cost.