MANG Problem #44: Race Car (Hard)

1. Problem Statement

Your car starts at position 0 and speed +1 on an infinite number line. Your car can go into negative positions.

You can issue the instructions 'A' (Accelerate) or 'R' (Reverse):

• 'A': position += speed, speed *= 2.
• 'R': If speed > 0 then speed = -1, else speed = 1. Your position stays the same.

Given a target position target, return the length of the shortest sequence of instructions to get there.

Input: target = 3
Output: 2 (Path: 'A', 'A' -> Pos: 0->1->3)

2. Approach: Shortest Path in State Space (BFS)

We want the "shortest sequence of instructions". This screams BFS. However, the graph isn't a grid of cells. The nodes are "States", defined by (position, speed).

1. Queue: Stores (position, speed, steps).
2. Visited Set: We must track (position, speed) to avoid infinite loops. A simple string pos + "," + speed works.
3. Transitions: From any state, we have exactly two choices:
   • A: Push (pos + speed, speed * 2, steps + 1).
   • R: Push (pos, speed > 0 ? -1 : 1, steps + 1).
4. Pruning: The number line is infinite. If we go too far past the target (e.g., pos > target * 2), or too far negative, we should stop exploring that branch.

3. Java Implementation

public int racecar(int target) {
    Queue<int[]> q = new LinkedList<>();
    q.offer(new int[]{0, 1, 0}); // position, speed, steps
    
    Set<String> visited = new HashSet<>();
    visited.add("0,1");
    
    while (!q.isEmpty()) {
        int[] curr = q.poll();
        int pos = curr[0], speed = curr[1], steps = curr[2];
        
        if (pos == target) return steps;
        
        // Choice 1: Accelerate
        int nextPos = pos + speed;
        int nextSpeed = speed * 2;
        String keyA = nextPos + "," + nextSpeed;
        
        // Prune search space: don't go wildly past the target
        if (Math.abs(nextPos) < 2 * target && !visited.contains(keyA)) {
            visited.add(keyA);
            q.offer(new int[]{nextPos, nextSpeed, steps + 1});
        }
        
        // Choice 2: Reverse
        nextPos = pos;
        nextSpeed = speed > 0 ? -1 : 1;
        String keyR = nextPos + "," + nextSpeed;
        
        if (Math.abs(nextPos) < 2 * target && !visited.contains(keyR)) {
            visited.add(keyR);
            q.offer(new int[]{nextPos, nextSpeed, steps + 1});
        }
    }
    return -1;
}

4. 5-Minute "Video-Style" Walkthrough

1. The Invisible Graph: There is no matrix or adjacency list here. The "graph" is generated on the fly. Every instruction creates a new edge to a new "State Node."
2. The State Memory: If you are at position 5 with speed 2, that is a completely different state than being at position 5 with speed -1. You must track BOTH in your visited set.
3. The Boundary Pruning: Why 2 * target? If the target is 10, accelerating to 31 before reversing is mathematically suboptimal. Bounding the search space prevents the BFS from running forever into infinity.

5. Interview Discussion

• Interviewer: "What is the time complexity?"
• You: "In the worst case, it's $O(T \log T)$ where $T$ is the target. The pruning ensures we only explore states within a constant factor of $T$, and the speed doubles logarithmically."
• Interviewer: "Can this be solved with Dynamic Programming?"
• You: "Yes. dp[i] could store the shortest instructions to reach i. We would evaluate sequences of 'A's that shoot past i and reverse, or fall short, reverse, and reverse again. DP is faster but much harder to reason about in a 45-minute interview."