Pilot a Rocket
You work for RocketX, a company that is going to send the first humans to colonize Mars. It is your job to write the algorithm that will connect the base on Earth to the space ship through a series of satellites to send instructions to pilot the rocket. It's important to connect to it quickly, so we need to find the shortest path from the base to the ship.
Given a graph data structure representing satellites, find the shortest path through the satellites to reach the target. You can always assume there will only be one shortest path.
The starting node will always be base and the ending node will be ship.
If the ship can't be reached, return null.
Write a function pilotRocket that takes a satellites input graph and returns an array of satellite IDs in the order that reaches the ship in the shortest path.
Breakdown
Approach and test strategy
A shortest unweighted route with BFS parent reconstruction
Read the approach, boundary cases, and complexity
Treat satellites as vertices and available moves as edges. A FIFO frontier explores reachable vertices in nondecreasing hop count. Mark a vertex at discovery and remember its parent then, so the first discovered route establishes a shortest unweighted path. Reconstruct the answer by following parents backward from the target. A depth-first discovery route can be valid without being shortest.
Cases to check
- Include a cycle so discovery marking must prevent repeated work.
- Provide routes of different lengths and check the shorter one.
- An unreachable ship returns null, which differs from an empty route.
Cost model
BFS scans O(V + E) reachable graph structure and uses O(V) frontier, discovery, and parent storage. Efficient FIFO removal is required to preserve that time bound.
Programming languages for this lesson
Starter code and reference implementations are available in:
The editor shows which of these languages can run on this deployment.
Validate My Answer
There are two ways to traverse graphs, but only one of the methods guarantees you'll use the shortest path.
Make sure your search algorithm doesn't get caught in a graph cycle.
Make sure your solution doesn't print in reverse order.
Make sure you handle the case when there is no path to the final node.
This can be solved in O(V + E) time where V is the number of vertices and E is the number of edges.
Pilot a Rocket
Given a graph data structure representing satellites, find the shortest path through the satellites to reach the target. You can always assume there will only be one shortest path.
The starting node will always be base and the ending node will be ship.
If the ship can't be reached, return null.
Write a function pilotRocket that takes a satellites input graph and returns an array of satellite IDs in the order that reaches the ship in the shortest path.