818. Race Car - Solution & Explanation

The problem

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):

When you get an instruction 'A', your car does the following:
- position += speed
- speed *= 2
When you get an instruction 'R', your car does the following:
- If your speed is positive then speed = -1
- otherwise speed = 1
Your position stays the same.

For 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 <= 10⁴

Approach overview

Problem 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 1: Breadth-First Search (BFS) Approach

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.

Python

from collections import deque

def racecar(target: int) -> int:
    queue = deque([(0, 1)])  # (position, speed)
    visited = set([(0, 1)])
    steps = 0
    
    while queue:
        for _ in range(len(queue)):
            position, speed = queue.popleft()
            
            if position == target:
                return steps
            
            # Accelerate
ew_position, new_speed = position + speed, speed * 2
            if (new_position, new_speed) not in visited and -0.5 * target <= new_position <= 1.5 * target:
                visited.add((new_position, new_speed))
                queue.append((new_position, new_speed))
            
            # Reverse
            new_position, new_speed = position, -1 if speed > 0 else 1
            if (new_position, new_speed) not in visited:
                visited.add((new_position, new_speed))
                queue.append((new_position, new_speed))
        
        steps += 1
    return -1

C++

#include <unordered_set>
#include <deque>
#include <tuple>
using namespace std;

int racecar(int target) {
    deque<tuple<int, int, int>> queue;  // (position, speed, steps)
    unordered_set<string> visited;
    queue.emplace_back(0, 1, 0);
    visited.insert("0,1");
    
    while (!queue.empty()) {
        auto [position, speed, steps] = queue.front();
        queue.pop_front();
        
        if (position == target) {
            return steps;
        }
        
        // Accelerate
        int new_position = position + speed;
        int new_speed = speed * 2;
        string state = to_string(new_position) + "," + to_string(new_speed);
        if (visited.find(state) == visited.end() && -0.5 * target <= new_position && new_position <= 1.5 * target) {
            visited.insert(state);
            queue.emplace_back(new_position, new_speed, steps + 1);
        }
        
        // Reverse
        new_position = position;
        new_speed = speed > 0 ? -1 : 1;
        state = to_string(new_position) + "," + to_string(new_speed);
        if (visited.find(state) == visited.end()) {
            visited.insert(state);
            queue.emplace_back(new_position, new_speed, steps + 1);
        }
    }
    return -1;
}

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.

Complexity

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.

Try this approach in the editor

Approach 2: Dynamic Programming Approach

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.

Java

class Solution {
    public int racecar(int target) {
        int[] dp = new int[target + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        return racecarHelper(target, dp);
    }
    
    private int racecarHelper(int target, int[] dp) {
        if (dp[target] < Integer.MAX_VALUE) return dp[target];
        int m = Integer.highestOneBit(target) << 1;
        if (m - 1 == target) {
            dp[target] = Integer.bitCount(m - 1);
        } else {
            dp[target] = racecarHelper(m - 1 - target, dp) + Integer.bitCount(m - 1) + 1;
            for (int back = 1; back < m / 2; ++back) {
                dp[target] = Math.min(dp[target], racecarHelper(target - (m / 2 - 1) + (1 << back) - 1, dp) + Integer.bitCount(m / 2 - 1) + 1 + back);
            }
        }
        return dp[target];
    }
}

public class Solution {
    public int Racecar(int target) {
        int[] dp = new int[target + 1];
        Array.Fill(dp, int.MaxValue);
        return RacecarHelper(target, dp);
    }

    private int RacecarHelper(int target, int[] dp) {
        if (dp[target] < int.MaxValue) return dp[target];
        int m = (1 << (int)Math.Ceiling(Math.Log2(target + 1)));
        if (m - 1 == target) {
            dp[target] = (int)Math.Log2(m);
        } else {
            dp[target] = RacecarHelper(m - 1 - target, dp) + (int)Math.Log2(m) + 1;
            for (int back = 1; back < m / 2; ++back) {
                dp[target] = Math.Min(dp[target], RacecarHelper(target - (m / 2 - 1) + (1 << back) - 1, dp) + (int)Math.Log2(m / 2) + 1 + back);
            }
        }
        return dp[target];
    }
}

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.

Complexity

Time Complexity: O(n log n), because of the dynamic states being calculated.
Space Complexity: O(n), needed to store the DP states.

Try this approach in the editor

Approach 3: Default Approach

func racecar(target int) int {
	dp := make([]int, target+1)
	for i := 1; i <= target; i++ {
		k := bits.Len(uint(i))
		if i == (1<<k)-1 {
			dp[i] = k
			continue
		}
		dp[i] = dp[(1<<k)-1-i] + k + 1
		for j := 0; j < k; j++ {
			dp[i] = min(dp[i], dp[i-(1<<(k-1))+(1<<j)]+k-1+j+2)
		}
	}
	return dp[target]
}

Try this approach in the editor

Complexity comparison

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). Space Complexity: O(n), due to the space required to store visited states.
Dynamic Programming Approach	Time Complexity: O(n log n), because of the dynamic states being calculated. Space Complexity: O(n), needed to store the DP states.
Default Approach	–

Complexity analysis

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.

Frequently asked questions

Is Race Car easy or hard?

Race Car is classified as a Hard problem. The difficulty comes from recognizing the exponential movement pattern created by repeated accelerations and converting that insight into a dynamic programming recurrence.

Race Car Python/Java solution

Python and C++ implementations commonly use BFS with a queue to explore (position, speed) states. Java and C# solutions often implement the dynamic programming recurrence that leverages positions of the form 2^k − 1 to compute the minimum instruction count.

How to solve Race Car in O(n)?

A strict O(n) solution is not typically achievable because each state requires evaluating bit-length transitions based on powers of two. The commonly accepted optimal approach is dynamic programming with O(n log n) time, which is efficient for targets up to the problem constraints.

What is the best approach for Race Car?

Dynamic programming with the bit-length observation (positions of the form 2^k − 1) is the most efficient approach. It reduces the search space by modeling the optimal sequence of accelerations and reversals for each target value. The solution runs in O(T log T) time and O(T) space.

Is Race Car asked at Google/Amazon/Meta?

Race Car is a well-known hard problem that appears in preparation sets for companies like Google, Amazon, and Meta. It tests graph modeling, BFS exploration, and dynamic programming optimization, which are common interview themes.

What data structure is used in Race Car?

The BFS approach uses a queue and a visited set to track explored states represented by (position, speed). The optimized solution uses a dynamic programming array combined with bit-length calculations to store minimum instruction counts.

What is the time complexity of Race Car?

Both the BFS and dynamic programming approaches run in roughly O(T log T) time, where T is the target position. BFS explores reachable states using a queue, while the DP approach computes optimal instruction counts for all positions up to the target.

Race Car solution and explanation

The problem

Approach overview

Approach 1: Breadth-First Search (BFS) Approach

Approach 2: Dynamic Programming Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Race Car solution and explanation

The problem

Approach overview

Approach 1: Breadth-First Search (BFS) Approach

Approach 2: Dynamic Programming Approach

Approach 3: Default Approach

Complexity comparison

Complexity analysis

Frequently asked questions

Comments

Related problems