818. Race Car

class Solution {
    public int racecar(int target) {
        // [position, speed]
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{0, 1});
        
        Set<String> visited = new HashSet<>();
        String key = String.valueOf(0) + "," + String.valueOf(1);
        visited.add(key);
        
        int steps = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                int[] cur = queue.poll();
                int pos = cur[0];
                int speed = cur[1];
                if (pos == target) {
                    return steps;
                }
                
                int nextPos = pos + speed;
                int nextSpeed = speed * 2;
                key = String.valueOf(nextPos) + "," + String.valueOf(nextSpeed);
                
                if (! visited.contains(key) && Math.abs(target - nextPos) < target) {
                    visited.add(key);
                    queue.offer(new int[]{nextPos, nextSpeed});
                }
                
                nextPos = pos;
                nextSpeed = speed < 0 ? 1 : -1;
                key = String.valueOf(nextPos) + "," + String.valueOf(nextSpeed);
                
                if (! visited.contains(key) && Math.abs(target - nextPos) < target) {
                    visited.add(key);
                    queue.offer(new int[]{nextPos, nextSpeed});
                }
            }
            steps += 1;
        }
        return -1;
    }
}