Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions. Your car drives automatically according to a sequence of instructions 'A' (accelerate) and 'R' (reverse):
'A', your car does the following:
position += speedspeed *= 2'R', your car does the following:
speed = -1speed = 1For example, after commands "AAR", your car goes to positions 0 --> 1 --> 3 --> 3, and your speed goes to 1 --> 2 --> 4 --> -1.
Given a target position target, return the length of the shortest sequence of instructions to get there.
Example 1:
Input: target = 3 Output: 2 Explanation: The shortest instruction sequence is "AA". Your position goes from 0 --> 1 --> 3.
Example 2:
Input: target = 6 Output: 5 Explanation: The shortest instruction sequence is "AAARA". Your position goes from 0 --> 1 --> 3 --> 7 --> 7 --> 6.
Constraints:
1 <= target <= 104Race Car is a classic state-search problem where a car starts at position 0 with speed 1 and must reach a target using two commands: accelerate (A) and reverse (R). The key challenge is minimizing the number of instructions while handling exponential movement caused by repeated accelerations.
A common strategy is dynamic programming with memoization. Observe that accelerating k times moves the car to 2^k - 1. Using this insight, we compare two scenarios: stopping exactly at the closest power-of-two distance or overshooting and reversing to approach the target from the other direction. The DP state stores the minimum instructions required to reach each distance.
Another viable approach is BFS over states, where each state tracks position and speed. BFS guarantees the shortest instruction sequence but requires pruning to avoid exponential growth. The DP approach is generally more efficient for large targets, reducing redundant exploration while leveraging mathematical structure in the movement pattern.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Dynamic Programming with Memoization | O(T log T) | O(T) |
| BFS State Exploration | O(T log T) | O(T) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Race Car can also be solved using breadth-first search by treating each state as a combination of position and speed. BFS guarantees the shortest sequence of commands but requires careful pruning to avoid exploring too many states.
Yes, Race Car is considered a challenging dynamic programming and state exploration problem that has appeared in advanced interview preparation sets. It tests understanding of BFS, DP optimization, and mathematical observation of movement patterns.
The optimal approach typically uses dynamic programming with memoization. It leverages the observation that repeated accelerations move the car to positions of the form 2^k - 1, allowing efficient transitions when overshooting or reversing toward the target.
For the dynamic programming approach, an array or hash map is used for memoization to store the minimum instructions for each target distance. In the BFS approach, a queue is used to process states level by level.