Race Car LeetCode Solution

Problem Statement

Race Car LeetCode Solution – Your car starts at the 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.

Input: target = 3
Output: 2
Explanation: 
The shortest instruction sequence is "AA".
Your position goes from 0 --> 1 --> 3.

Explanation

Well, the BFS solution is straightforward: we can keep track of all the possible positions of the racecar after n instructions (n = 0, 1, 2, 3, 4, ...) and return the smallest n such that the target position is reached. Naive BFS will run at O(2^n) since for each position, we have two choices: either accelerate or reverse. Further observations reveal that there may be overlapping among intermediate states so we need to memorize visited states (each state is characterized by two integers: car position and car speed). However, the total number of unique states still blows up for large target positions (because the position and speed can grow unbounded), so we need further pruning of the search space.

Code

C++ Code For Race Car

class CarAttributes{
private:
    int position,speed;

public:
    CarAttributes(int position,int speed)
    {
        this->position = position;
        this->speed = speed;
    }

    void setPosition(int position)
    {
        this->position = position;
    }

    void setSpeed(int speed)
    {
        this->speed = speed;
    }

    int getPosition()
    {
        return position;
    }

    int getSpeed()
    {
        return speed;
    }
    
};


class Solution {
    int target;
    
    bool isPositionNotFarFromTarget(int position,int target)
    {
        return abs(target - position) < target;
    }
    
    bool isValidInstruction(int position,unordered_set<string> &visSet,string &key,int target)
    {
        return !visSet.count(key) and isPositionNotFarFromTarget(position,target);
    }
    
    int getMinimumNumberOfInstructions()
    {
        int minimumNumberOfInstructions = 0;
        queue<CarAttributes> bfsQueue;
        unordered_set<string> visSet;
        string key = to_string(0) + "," + to_string(1);
        visSet.insert(key);
        bfsQueue.push(CarAttributes(0,1));
        
        // lambda function to deal with repititive work.
        auto moveToNextPos = [&](int nextPosition,int nextSpeed,CarAttributes &carAttribute,string &key){
            visSet.insert(key);
            carAttribute.setPosition(nextPosition);
            carAttribute.setSpeed(nextSpeed);
            bfsQueue.push(carAttribute);
        };
        
        while(!bfsQueue.empty())
        {
            int size = (int)bfsQueue.size();
            while(size--)
            {
                CarAttributes front = bfsQueue.front();
                bfsQueue.pop();
                int currPos = front.getPosition();
                int currSpd = front.getSpeed();

                if(currPos == target)
                return minimumNumberOfInstructions;

                // Explore option : "A" 
                int nextPos = currPos + currSpd;
                int nextSpd = currSpd * 2;
                key = to_string(nextPos) + "," + to_string(nextSpd);
                if(isValidInstruction(nextPos,visSet,key,target))
                {
                    moveToNextPos(nextPos,nextSpd,front,key);
                }
                
                // Explore option : "R"
                nextPos = currPos;
                nextSpd = currSpd < 0 ? 1 : -1;
                key = to_string(nextPos) + "," + to_string(nextSpd);
                if(isValidInstruction(nextPos,visSet,key,target))
                {
                     moveToNextPos(nextPos,nextSpd,front,key);
                }

            }
            minimumNumberOfInstructions += 1;
        }
        return -1;
    }

public:
    int racecar(int target) 
    {
        this->target = target;
        return getMinimumNumberOfInstructions();
    }
};

Java Code For Race Car

    class CarInfo{
        int pos, speed;
        public CarInfo(int p, int s) {
            pos = p;
            speed = s;
        }
    }
class Solution {

    public int racecar(int target) {

        Set<String> visited = new HashSet<>();
        String begin = 0 + "/" + 1;
        visited.add(begin);
        Queue<CarInfo> queue = new LinkedList<>();
        queue.add(new CarInfo(0,1));
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for(int i = 0; i < size; i++) {
                CarInfo cur = queue.poll();
                if (cur.pos == target) return level;
                String s1 = (cur.pos + cur.speed) + "/" + (cur.speed * 2);
                String s2 = cur.pos + "/" + (cur.speed > 0 ? -1 : 1);
                if (Math.abs(cur.pos + cur.speed - target) < target && !visited.contains(s1)) {
                    visited.add(s1);
                    queue.add(new CarInfo(cur.pos + cur.speed, cur.speed * 2));
                }
                if (Math.abs(cur.pos - target) < target && !visited.contains(s2)) {
                    visited.add(s2);
                    queue.add(new CarInfo(cur.pos, cur.speed > 0 ? -1 : 1));
                }
            }
            
            level++;
        }
        return -1;

    }
}

Python Code For Race Car

class Solution:
    def racecar(self, target: int) -> int:
        
        #1. Initialize double ended queue as 0 moves, 0 position, +1 velocity
        queue = collections.deque([(0, 0, 1)])
        while queue:
            
            # (moves) moves, (pos) position, (vel) velocity)
            moves, pos, vel = queue.popleft()

            if pos == target:
                return moves
            
            #2. Always consider moving the car in the direction it is already going
            queue.append((moves + 1, pos + vel, 2 * vel))
            
            #3. Only consider changing the direction of the car if one of the following conditions is true
            #   i.  The car is driving away from the target.
            #   ii. The car will pass the target in the next move.  
            if (pos + vel > target and vel > 0) or (pos + vel < target and vel < 0):
                queue.append((moves + 1, pos, -vel / abs(vel)))

Complexity Analysis for Race Car LeetCode Solution

Time Complexity :

BFS traversal takes O(V + E)

Space Complexity

Space required by Queue is: O(E)