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.
The BFS approach treats each state represented by (position, speed) as a node in a graph. The solution involves exploring the shortest path from the starting state (0, 1) to the target by performing actions 'A' (accelerate) and 'R' (reverse). BFS is used because it explores all possibilities at the current level before moving deeper, which aligns with finding the shortest sequence of instructions.
The BFS algorithm starts at (0, 1) and explores all possible states by enqueuing the results of the 'A' (accelerate) and 'R' (reverse) operations. A set is used to keep track of visited states to avoid redundant calculations and infinite loops. As soon as the target position is reached, the function returns the number of steps taken.
Time Complexity: O(2^n), where n is the number of operations (upper bound due to the binary operations).
Space Complexity: O(n), due to the space required to store visited states.
The DP approach breaks down the problem into smaller subproblems. It involves building an array dp where each element at index i represents the minimum number of steps required to reach position i. The approach relies on determining whether to accelerate or reverse to achieve the least number of instructions.
This Java solution establishes a recursive DP helper function, which iteratively determines the minimal instruction count. By considering acceleration to the nearest power of two and introducing potential reversals, the minimum steps are ascertained.
Time Complexity: O(n log n), because of the dynamic states being calculated.
Space Complexity: O(n), needed to store the DP states.
| Approach | Complexity |
|---|---|
| Breadth-First Search (BFS) Approach | Time Complexity: O(2^n), where n is the number of operations (upper bound due to the binary operations). |
| Dynamic Programming Approach | Time Complexity: O(n log n), because of the dynamic states being calculated. |
| Default Approach | — |
| 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. |
RACE CAR | LEETCODE # 818 | PYTHON BFS SOLUTION • Cracking FAANG • 14,895 views views
Watch 9 more video solutions →Practice Race Car with our built-in code editor and test cases.
Practice on FleetCode