818. Race Car

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.

 

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

 

Solutions

Solution: Breadth-First Search

• Time complexity: O(2^steps)
• Space complexity: O(2^steps)

 

JavaScript

/**
 * @param {number} target
 * @return {number}
 */
const racecar = function (target) {
  let queue = [{ position: 0, speed: 1 }];
  let result = 0;

  while (queue.length) {
    const nextQueue = [];

    for (const { position, speed } of queue) {
      const nextPosition = position + speed;

      if (nextPosition === target) return result + 1;
      nextQueue.push({ position: nextPosition, speed: speed * 2 });

      if (speed > 0 && nextPosition < target) continue;
      if (speed < 0 && nextPosition > target) continue;
      nextQueue.push({ position, speed: speed > 0 ? -1 : 1 });
    }
    result += 1;
    queue = nextQueue;
  }
  return 0;
};

 

Solution: Dynamic Programming

• Time complexity: O(target*log(target))
• Space complexity: O(target)

 

JavaScript

/**
 * @param {number} target
 * @return {number}
 */
const racecar = function (target) {
  const dp = new Array(target + 1).fill(-1);

  const raceTo = distance => {
    if (dp[distance] > -1) return dp[distance];

    let steps = 1;
    let currentPosition = 1;
    let result = Number.MAX_SAFE_INTEGER;

    while (currentPosition < distance) {
      let reverseSteps = 0;
      let reversePosition = 0;

      while (reversePosition < currentPosition) {
        const remainDistance = distance - (currentPosition - reversePosition);

        result = Math.min(steps + reverseSteps + 2 + raceTo(remainDistance), result);
        reverseSteps += 1;
        reversePosition = (1 << reverseSteps) - 1;
      }
      steps += 1;
      currentPosition = (1 << steps) - 1;
    }
    const overflowDistance = currentPosition - distance;
    const needSteps = overflowDistance ? 1 + raceTo(overflowDistance) : 0;

    result = Math.min(steps + needSteps, result);
    return (dp[distance] = result);
  };

  return raceTo(target);
};