Skip to main content
Talentd

Race Car - Solution & Explanation

HardDynamic Programming9 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

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 <= 104

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.

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.

Code

PythonC++

Python

C++

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.

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.

Code

JavaC#

Java

C#

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

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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—

Detailed Complexity Analysis

ApproachTimeSpaceWhen 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.

Video Solution

RACE CAR | LEETCODE # 818 | PYTHON BFS SOLUTION • Cracking FAANG • 15,236 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Race Car with our built-in code editor and test cases.

Practice on FleetCode
Previous

Longest Palindromic Substring

Next

Regular Expression Matching