Problem

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 = 1Your 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.

Examples

Example 1

1
2
3
4
5

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

Example 2

1
2
3
4
5

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 <= 10^4

Solution

Method 1 – Dynamic Programming with BFS

Intuition

To reach the target position with the shortest sequence, we can use BFS to explore all possible states (position, speed) and keep track of the minimum steps to reach each state. Dynamic programming (memoization) helps avoid revisiting states.

Approach

  1. Use BFS to explore states: (position, speed).
  2. For each state, try two actions:
    • Accelerate: move to (pos+speed, speed*2).
    • Reverse: change speed to -1 or 1 depending on current speed.
  3. Use a set or map to avoid revisiting states.
  4. Stop when reaching the target position.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class Solution {
public:
    int racecar(int target) {
        queue<pair<int,int>> q;
        unordered_set<string> vis;
        q.push({0,1});
        vis.insert("0,1");
        int steps = 0;
        while (!q.empty()) {
            int sz = q.size();
            while (sz--) {
                auto [pos, speed] = q.front(); q.pop();
                if (pos == target) return steps;
                // Accelerate
                int npos = pos + speed, nspeed = speed * 2;
                string key1 = to_string(npos) + "," + to_string(nspeed);
                if (abs(npos) <= 2*target && !vis.count(key1)) {
                    vis.insert(key1);
                    q.push({npos, nspeed});
                }
                // Reverse
                int rspeed = speed > 0 ? -1 : 1;
                string key2 = to_string(pos) + "," + to_string(rspeed);
                if (!vis.count(key2)) {
                    vis.insert(key2);
                    q.push({pos, rspeed});
                }
            }
            steps++;
        }
        return -1;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

func racecar(target int) int {
    type state struct{pos, speed int}
    q := []state{{0,1}}
    vis := map[state]bool{{0,1}:true}
    steps := 0
    for len(q) > 0 {
        nq := []state{}
        for _, s := range q {
            if s.pos == target { return steps }
            npos, nspeed := s.pos+s.speed, s.speed*2
            ns := state{npos, nspeed}
            if abs(npos) <= 2*target && !vis[ns] {
                vis[ns] = true
                nq = append(nq, ns)
            }
            rspeed := 1
            if s.speed > 0 { rspeed = -1 }
            rs := state{s.pos, rspeed}
            if !vis[rs] {
                vis[rs] = true
                nq = append(nq, rs)
            }
        }
        q = nq
        steps++
    }
    return -1
}
func abs(x int) int { if x < 0 { return -x }; return x }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

import java.util.*;
class Solution {
    public int racecar(int target) {
        Queue<int[]> q = new LinkedList<>();
        Set<String> vis = new HashSet<>();
        q.offer(new int[]{0,1});
        vis.add("0,1");
        int steps = 0;
        while (!q.isEmpty()) {
            int sz = q.size();
            for (int i = 0; i < sz; i++) {
                int[] cur = q.poll();
                int pos = cur[0], speed = cur[1];
                if (pos == target) return steps;
                int npos = pos + speed, nspeed = speed * 2;
                String key1 = npos + "," + nspeed;
                if (Math.abs(npos) <= 2*target && !vis.contains(key1)) {
                    vis.add(key1);
                    q.offer(new int[]{npos, nspeed});
                }
                int rspeed = speed > 0 ? -1 : 1;
                String key2 = pos + "," + rspeed;
                if (!vis.contains(key2)) {
                    vis.add(key2);
                    q.offer(new int[]{pos, rspeed});
                }
            }
            steps++;
        }
        return -1;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

import java.util.*
class Solution {
    fun racecar(target: Int): Int {
        val q: Queue<Pair<Int,Int>> = LinkedList()
        val vis = mutableSetOf<Pair<Int,Int>>()
        q.add(0 to 1)
        vis.add(0 to 1)
        var steps = 0
        while (q.isNotEmpty()) {
            repeat(q.size) {
                val (pos, speed) = q.remove()
                if (pos == target) return steps
                val npos = pos + speed
                val nspeed = speed * 2
                if (Math.abs(npos) <= 2*target && vis.add(npos to nspeed)) {
                    q.add(npos to nspeed)
                }
                val rspeed = if (speed > 0) -1 else 1
                if (vis.add(pos to rspeed)) {
                    q.add(pos to rspeed)
                }
            }
            steps++
        }
        return -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

def racecar(target: int) -> int:
    from collections import deque
    q = deque([(0,1)])
    vis = {(0,1)}
    steps = 0
    while q:
        for _ in range(len(q)):
            pos, speed = q.popleft()
            if pos == target:
                return steps
            npos, nspeed = pos+speed, speed*2
            if abs(npos) <= 2*target and (npos, nspeed) not in vis:
                vis.add((npos, nspeed))
                q.append((npos, nspeed))
            rspeed = -1 if speed > 0 else 1
            if (pos, rspeed) not in vis:
                vis.add((pos, rspeed))
                q.append((pos, rspeed))
        steps += 1
    return -1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

use std::collections::{HashSet, VecDeque};
impl Solution {
    pub fn racecar(target: i32) -> i32 {
        let mut q = VecDeque::new();
        let mut vis = HashSet::new();
        q.push_back((0,1));
        vis.insert((0,1));
        let mut steps = 0;
        while !q.is_empty() {
            for _ in 0..q.len() {
                let (pos, speed) = q.pop_front().unwrap();
                if pos == target { return steps; }
                let npos = pos + speed;
                let nspeed = speed * 2;
                if npos.abs() <= 2*target && vis.insert((npos, nspeed)) {
                    q.push_back((npos, nspeed));
                }
                let rspeed = if speed > 0 { -1 } else { 1 };
                if vis.insert((pos, rspeed)) {
                    q.push_back((pos, rspeed));
                }
            }
            steps += 1;
        }
        -1
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

class Solution {
    racecar(target: number): number {
        const q: [number, number][] = [[0, 1]];
        const vis = new Set<string>(['0,1']);
        let steps = 0;
        while (q.length) {
            const sz = q.length;
            for (let i = 0; i < sz; i++) {
                const [pos, speed] = q.shift()!;
                if (pos === target) return steps;
                const npos = pos + speed, nspeed = speed * 2;
                const key1 = `${npos},${nspeed}`;
                if (Math.abs(npos) <= 2*target && !vis.has(key1)) {
                    vis.add(key1);
                    q.push([npos, nspeed]);
                }
                const rspeed = speed > 0 ? -1 : 1;
                const key2 = `${pos},${rspeed}`;
                if (!vis.has(key2)) {
                    vis.add(key2);
                    q.push([pos, rspeed]);
                }
            }
            steps++;
        }
        return -1;
    }
}

Complexity

  • ⏰ Time complexity: O(T log T), where T is the target value, since the state space is bounded by position and speed.
  • 🧺 Space complexity: O(T log T), for the visited states.

Method 2 -

Code

Complexity

  • Time: O(nnnxxxnnn)
  • Space: O(nnnxxx)