Race Car

Hard Dynamic Programming 1D DP Original on LeetCode

Reported atGoogle

Race Car is a hard dynamic programming problem solved with the 1d dp pattern. The best approach, optimal (dp on distance), runs in O(T log T) time and O(T) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (bfs over position and speed) up.

Problem

A car sits at position 0 on an endless number line with speed +1. It obeys two instructions:

  • A (accelerate): position += speed, then speed *= 2.
  • R (reverse): the speed becomes -1 if it was positive, otherwise +1. The position does not change.

Given a positive integer target, return the length of the shortest instruction string that leaves the car at exactly target.

Examples

Example 1

Input
target = 7
Output
3
Why
"AAA" moves the car 1 + 2 + 4 = 7, ending exactly on 7.

Example 2

Input
target = 5
Output
7
Why
"AARARAA": reach 3, turn, back up to 2, turn again, then two A's go 2 -> 3 -> 5. No shorter string ends on 5.

Example 3

Input
target = 2
Output
4
Why
"AARA" goes to 3, turns, and steps back to 2.

Constraints

  • 1 <= target <= 10^4

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 13 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (BFS over position and speed)O(T log T)O(T log T)
Optimal (DP on distance)O(T log T)O(T)

1Brute force (BFS over position and speed)

TimeO(T log T)Positions are limited to about 4T values and speeds to about log T powers of two in each direction, and each state is processed once.
SpaceO(T log T)The visited set and queue can hold every reachable state.

Treat (position, speed) as a graph node. A and R are the two edges out of every node, each of cost 1, so a breadth-first search from (0, 1) finds the fewest instructions. Positions far beyond the target are never useful, so they are pruned.

  1. Start a queue with (0, 1) and a visited set.
  2. Process the queue level by level; the level number is the instruction count.
  3. If the position equals the target, return the level.
  4. Accelerate: (pos + speed, speed * 2), kept only if |new pos| <= 2 * target.
  5. Reverse: (pos, -1 if speed > 0 else 1).
  6. Add each unseen state to the queue.
class Solution {
    public int racecar(int target) {
        Deque<int[]> queue = new ArrayDeque<>();
        Set<Long> seen = new HashSet<>();
        queue.add(new int[] { 0, 1 });
        seen.add(key(0, 1));
        int steps = 0;
        while (!queue.isEmpty()) {
            for (int size = queue.size(); size > 0; size--) {
                int[] cur = queue.poll();
                int pos = cur[0], speed = cur[1];
                if (pos == target) return steps;
                int np = pos + speed, ns = speed * 2;
                if (Math.abs(np) <= 2 * target && seen.add(key(np, ns))) {
                    queue.add(new int[] { np, ns });
                }
                int rs = speed > 0 ? -1 : 1;
                if (seen.add(key(pos, rs))) {
                    queue.add(new int[] { pos, rs });
                }
            }
            steps++;
        }
        return -1;
    }

    private long key(int pos, int speed) {
        return (long) pos * 1_000_000L + speed;
    }
}

2Optimal (DP on distance)

TimeO(T log T)Each of the T distances tries at most log T values of m.
SpaceO(T)One dp array of size T + 1.

Let dp[t] be the fewest instructions to cover distance t starting at speed 1. If t has k bits, k A's reach 2^k - 1. If that is exactly t, the answer is k. Otherwise either overshoot to 2^k - 1, reverse, and cover the leftover 2^k - 1 - t (which is a fresh problem from speed 1), or stop at 2^(k-1) - 1, reverse, back up 2^m - 1 with m A's, reverse again, and cover what remains forwards. Every leftover distance is smaller than t.

  1. For t from 1 to target, let k be the bit length of t.
  2. If t == 2^k - 1, dp[t] = k.
  3. Otherwise start with dp[t] = k + 1 + dp[2^k - 1 - t] (overshoot, reverse).
  4. For each m from 0 to k - 2, try (k - 1) + 1 + m + 1 + dp[t - (2^(k-1) - 1) + (2^m - 1)].
  5. Return dp[target].
class Solution {
    public int racecar(int target) {
        int[] dp = new int[target + 1];
        for (int t = 1; t <= target; t++) {
            int k = 32 - Integer.numberOfLeadingZeros(t);
            if (t == (1 << k) - 1) {
                dp[t] = k;
                continue;
            }
            dp[t] = k + 1 + dp[(1 << k) - 1 - t];
            for (int m = 0; m < k - 1; m++) {
                int rest = t - ((1 << (k - 1)) - 1) + ((1 << m) - 1);
                dp[t] = Math.min(dp[t], (k - 1) + 1 + m + 1 + dp[rest]);
            }
        }
        return dp[target];
    }
}

Edge cases to test

  • Targets of the form 2^k - 1 (1, 3, 7, 15...), reached with only A's
  • Targets just past 2^k - 1, where overshooting and coming back competes with stopping early
  • target = 1

Hints

Hint 1

Each state of the car is just its position and its speed. Every instruction costs 1, so the shortest sequence is a shortest path.

Hint 2

After k A's from speed 1 the car has moved 2^k - 1. For a target t with k bits, either drive to 2^k - 1 (past t) and solve the rest backwards, or stop at 2^(k-1) - 1, turn, back up a little, turn again and solve the rest forwards.

Hint 3

Both options leave a smaller distance to cover, so dp[t] can be built from dp of smaller values.

FAQ

What is the best time complexity for Race Car?

Optimal (DP on distance) runs in O(T log T) time and O(T) extra space. Each of the T distances tries at most log T values of m.

Which pattern does Race Car use?

It is a dynamic programming problem that uses the 1d dp pattern. Other problems with the same pattern: Fibonacci Number, Climbing Stairs, Min Cost Climbing Stairs (2 jumps).

Is there a brute force solution for Race Car?

Yes. Brute force (BFS over position and speed) takes O(T log T) time and O(T log T) space. Treat (position, speed) as a graph node.

Which edge cases should I test for Race Car?

Targets of the form 2^k - 1 (1, 3, 7, 15...), reached with only A's; Targets just past 2^k - 1, where overshooting and coming back competes with stopping early; target = 1.