Problem Description

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.

Constraints:

• 1 <= target <= 10**4

https://leetcode.com/problems/race-car/

Examples

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

How to Solve

For this problem, a couple of approaches are there: dynamic programming, breadth-first search, or priority queue (heap). Among those, the solution here took the breadth-first search approach. It is a relatively simple solution. In the queue, the solution saves position and speed pairs. When the race car goes forward, (position + speed, speed * 2) will be added to the queue as a next state. The race car is allowed to go back. When the speed is negative and position + speed is less than the target, or the speed is positive and position + speed is greater than the target, the backward move has an effect. As the problem describes, the position stays the same. So, (position, backward speed of -1 or 1) will be added to the queue as a next state.

Solution

• C++
• Java
• JavaScript
• Python
• Ruby

• class RaceCar {
  public:
      int racecar(int target) {
          queue<pair<long long int, long long int>> q;  // position, speed
          q.push({0, 1});
          int steps = 0;
          while (!q.empty()) {
              int q_len = q.size();
              for (auto i = 0; i < q_len; ++i) {
                  auto [p, s] = q.front();
                  q.pop();
                  if (p == target) { return steps; }
                  q.push({p + s, s * 2});
                  int back = s > 0 ? -1 : 1;
                  if (((p + s) < target && s < 0) || ((p + s) > target && s > 0)) {
                      q.push({p, back});
                  }
              }
              ++steps;
          }
          return -1;
      }
  };
  

• class RaceCar:
      def racecar(self, target: int) -> int:
          q = [(0, 1)] # position, speed
          steps = 0
          while q:
              q_len = len(q)
              for i in range(q_len):
                  p, s = q.pop(0)
                  if p == target:
                      return steps
                  q.append((p + s, s * 2))
                  back = -1 if s > 0 else 1
                  if ((p + s) < target and s < 0) or\
                      ((p + s) > target and s > 0):
                      q.append((p, back))
              steps += 1
  

Complexities

• Time: O(t) – t: target
• Space: O(t)