Leetcode 1654 - Minimum Jumps to Reach Home

Subscribe Send me a message home page tags


Description

Leetcode 1654

A certain bug's home is on the x-axis at position x. Help them get there from position 0.

The bug jumps according to the following rules:

The bug may jump forward beyond its home, but it cannot jump to positions numbered with negative integers.

Given an array of integers forbidden, where forbidden[i] means that the bug cannot jump to the position forbidden[i], and integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If there is no possible sequence of jumps that lands the bug on position x, return -1.

Example 1:

Input: forbidden = [14,4,18,1,15], a = 3, b = 15, x = 9
Output: 3
Explanation: 3 jumps forward (0 -> 3 -> 6 -> 9) will get the bug home.

Example 2:

Input: forbidden = [8,3,16,6,12,20], a = 15, b = 13, x = 11
Output: -1

Example 3:

Input: forbidden = [1,6,2,14,5,17,4], a = 16, b = 9, x = 7
Output: 2
Explanation: One jump forward (0 -> 16) then one jump backward (16 -> 7) will get the bug home.

Solution

The formulation of this problem is a standard search problem so the first step is to define a state. Obviously, the state should contain the position information. In additional to that, we also need to track if we can go backwards. As the objective is to calculate the minimum steps, we can include the number of steps in the state as well.

Therefore, we have the following definition:

State {
    int position;
    int step;
    bool canGoBackwards;
}

The initial state is State(0, 0, false) and the target state is State(targetPosition, ?, ?) and the problem becomes very similar to a shortest path search problem. One of the classic algorithms to solve this type of problems is BFS.

There is room for optimization because this problem has customized conditions. For example, instead of doing the layer-by-layer standard BFS, we can mix BFS with DFS (e.g. go as far as possible). Another optimization is that if State(position, step, true) is visited then we can skip State(position, step, false) because we know it will not produce better results. (This is not implemented.)

One important question is when we can terminate the search and claim there is no solution. Note that all the input values are less than 2000. We can show that if the current position is larger than, for example 6000, then we can stop because continuing the search is pointless.

Suppose \( b > a \) and \( b = ka + l \) with \( 0 \leq l < b\). Then we can stop when the current position is larger than maximum forbidden position plus b plus l (i.e. beyond the red point in the figure below). The reason is that if the current position is beyond the red point, we can always go left by \(l\) unit distance because going backwards will not hit any forbidden positions. Therefore, if \( z \geq \textrm{max forbidden position} + l + b\) and we can reach home from \(z\), then we can also reach home from \(z - l\).

analysis.png

Implementation

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
namespace std {
    using _State = pair<int, bool>;
    template<>
    struct hash<_State> {
        std::size_t operator()(const _State& s) const {
            return s.second ? s.first : -s.first;
        }
    };
}

class State {
    public:
        int x;
        int step;
        bool canGoBackwards;
        State(int x_in, int step_in, bool canGoBackwards_in): x(x_in), step(step_in), canGoBackwards(canGoBackwards_in) {};
};



class Solution {

public:
    int targetPosition;
    int a;
    int b;
    unordered_set<int> forbiddenPositions{};
    unordered_set<pair<int, bool>> visitedStates{};

    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        if (x == 0) {
            return 0;
        }

        queue<State> stateQueue{};
        State initialState{0, 0, false};
        stateQueue.push(initialState);
        this->targetPosition = x;
        this->a = a;
        this->b = b;


        for (const auto&  fp : forbidden) {
            this->forbiddenPositions.insert(fp);
        }

        if (this->isForbidden(x)) {
            return -1;
        }

        int result = -1;

        while (!stateQueue.empty()) {
            State currentState = stateQueue.front();
            stateQueue.pop();

            if (result != -1 && currentState.step >= result) {
                return result;
            }


            if (!this->isVisited(currentState.x, currentState.canGoBackwards)) {

                // search ahead
                int position = currentState.x + a;
                int step = currentState.step;
                while (position < this->targetPosition && !this->isForbidden(position)) {
                    ++step;
                    stateQueue.emplace(position, step, true);
                    position += a;
                }

                this->visitedStates.insert(make_pair(currentState.x, currentState.canGoBackwards));

                if (currentState.canGoBackwards) {
                    int nextPosition = currentState.x - b;
                    if (this->isTargetPosition(nextPosition)) {
                        result = currentState.step + 1;
                    } else if (!this->isForbidden(nextPosition) && !this->isVisited(nextPosition, false)) {
                        stateQueue.emplace(nextPosition, currentState.step + 1, false);
                    }
                }

                int nextPosition = currentState.x + a;
                if (this->isTargetPosition(nextPosition)) {
                    result =  currentState.step + 1;
                } else if (!this->isForbidden(nextPosition) && !this->isVisited(nextPosition, true)) {
                    stateQueue.emplace(nextPosition, currentState.step + 1, true);
                }
            }
        }

        return result;
    }

    int isTargetPosition(const int& position) {
        return position == this->targetPosition;
    }

    bool isForbidden(const int& x) {
        if (x < 0 || x > 6000) {
            return true;
        } else {
            return this->forbiddenPositions.find(x) != this->forbiddenPositions.end();
        }
    }

    bool isVisited(const int position, const bool canGoBackwards) {
        return this->visitedStates.find(make_pair(position, canGoBackwards)) != this->visitedStates.end();
    }
};

----- END -----

Welcome to join reddit self-learning community.
Send me a message Subscribe to blog updates

Want some fun stuff?

/static/shopping_demo.png