Watch 10 video solutions for Race Car, a hard level problem involving Dynamic Programming. This walkthrough by Cracking FAANG has 14,895 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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 <= 104Problem Overview: You control a car starting at position 0 with speed 1. Instruction A doubles the speed and moves forward, while R reverses direction. The task is to reach a given target position using the minimum number of instructions.
Approach 1: Breadth-First Search (BFS) (Time: O(T log T), Space: O(T))
This approach models the problem as a state graph where each state is (position, speed). From every state you generate two transitions: accelerate (A) or reverse (R). BFS explores states level by level, guaranteeing the first time you reach the target uses the minimum number of instructions. A queue processes states while a visited set avoids revisiting the same (position, speed) combination. To keep the search bounded, states that move far beyond the target are pruned. BFS works well because instruction count is the metric being minimized. This is a classic shortest-path search over an implicit graph using breadth-first search.
Approach 2: Dynamic Programming with Bit Length Insight (Time: O(T log T), Space: O(T))
The optimal solution uses dynamic programming with a key observation: after k accelerations, the car reaches position 2^k - 1. For each target t, compute the smallest k where 2^k - 1 >= t. If 2^k - 1 == t, the answer is simply k. Otherwise two strategies exist: overshoot the target with k accelerations then reverse, or stop before the target with k-1 accelerations, reverse, move back for m steps, and then continue toward the target. The DP recurrence tries both options and picks the minimum instruction count. This reduces the exponential search space into overlapping subproblems and builds answers for all positions up to target. The algorithm repeatedly uses bit-length calculations and cached results, making it efficient even for targets near the upper constraint.
Recommended for interviews: Interviewers typically expect the dynamic programming solution because it shows pattern recognition and mathematical reasoning about 2^k - 1 positions. Implementing BFS first demonstrates understanding of shortest-path modeling, but recognizing the DP recurrence shows stronger algorithmic depth.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Breadth-First Search (State Graph) | O(T log T) | O(T) | Good for understanding the shortest-path nature of the problem and easy to implement for moderate targets. |
| Dynamic Programming (Bit-Length Strategy) | O(T log T) | O(T) | Preferred optimal solution for large targets and common interview expectation. |