Problem statement

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

Solution

One way to solve this problem is to use bfs with states (place, speed). It can be shown, that it is enough to visit only places with values between -2*target, 2*target. Also notice, that speed always is power of two, so there will be O(n log n) different states, where n = target. Next, what we do, we perform usual bfs. One important thing about bfs here, that we first need to check if state is visited and then put it to queue, in opposite case we can have several equal elements in queue. It is OK to put it before, if we working with trees, like in problem 0742, but not here.

Complexity

Finally, time and space complexity will be O(n log n).

Code

class Solution:
    def racecar(self, target):
        queue, visited = deque([(0, 1, 0)]), set([(0, 1)])
        LIMIT = target*2
        
        while queue:
            pos, speed, steps = queue.popleft()
            if pos == target: return steps
        
            cand1, cand2 = (pos+speed, speed<<1), (pos, -speed//abs(speed))
            if abs(pos+speed) <= LIMIT and cand1 not in visited:
                visited.add(cand1)
                queue.append((pos+speed, speed<<1, steps + 1))
            if cand2 not in visited:
                visited.add(cand2)
                queue.append((pos, -speed//abs(speed), steps + 1))

Remark

There is also Dijkstra solution: we can notice, that every optimal path will look like: we make several steps to the right, then several steps to the left, then again to the right ans so on, so final target will be equal to $(2^{k_1} - 1) - (2^{k_2} - 1) + (2^{k_3} - 1) - \dots $. However in practice it works almost the same as bfs.

There is also dp solution, with the same complexity, but it works 3-4 times faster. Also, there is one cheat on leetcode, which can increase speed dramatically: if we define dp outside our function, we will hash solutions for for smaller sub-problems.

Finally, there is greedy strategy, which I do not completely understand.