30. A* Search

Hard

Topics

Helpful tools to learn & understand

Visualize LogicActive Simulator

Watch key transitions, pointers, and variables update step-by-step.

Open

Check Solutions

Read clean, documented implementations across multiple patterns.

View Code

Thinkpad (Draw & Note)

Sketch diagrams on an infinite canvas and draft notes directly inline.

Draw

Example 1:

Input: grid = [[0,0,0],[0,1,0],[0,0,0]], start = [0,0], goal = [2,2]

Output: [[0, 0], [0, 1], [0, 2], [1, 2], [2, 2]]

Explanation: The shortest path from (0,0) to (2,2) avoids the obstacle at (1,1).

Example 2:

Input: grid = [[0,0,0],[0,1,0],[0,1,0]], start = [0,0], goal = [2,0]

Output: [[0, 0], [1, 0], [2, 0]]

Explanation: The shortest path from (0,0) to (2,0) directly downwards.

Example 3:

Input: grid = [[1,1,1],[1,1,1],[1,1,1]], start = [0,0], goal = [2,2]

Output: []

Explanation: No path exists because the grid is completely blocked by obstacles.

Example 4:

Input: grid = [[0,0,0],[0,0,0],[0,0,0]], start = [0,0], goal = [2,2]

Output: [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]]

Explanation: A possible shortest path from the top-left to bottom-right corner of a grid.

Example 5:

Input: grid = [[0,1,0,0,0],[0,1,0,1,0],[0,0,0,1,0],[0,1,1,1,0],[0,0,0,0,0]], start = [0,0], goal = [4,4]

Output: [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2], [3, 2], [4, 2], [4, 3], [4, 4]]

Explanation: The shortest path avoids several obstacles to reach the destination.

Constraints:

Time Complexity

O(b^d)

Space Complexity