Minimum Jumps To Reach Home - Leetcode Solution

The problem "Minimum Jumps to Reach Home" on LeetCode asks to find the minimum number of jumps required to reach home from a starting point, with some conditions applied.

The conditions are as follows:

• There is a fence on the left side
• There are certain forbidden places, called "forbidden", which we cannot step on
• We can only move forward, not backward
• We can jump to the right by exactly "a" units or "b" units at a time
• We cannot jump onto a forbidden place

The function takes four arguments:

• an array of "forbidden" positions
• an integer "a" (jump size)
• an integer "b" (jump size)
• an integer "x" (the position of our house)

The approach to solve this problem is to use breadth-first-search (BFS) to traverse all possible paths, while keeping track of the steps taken, forbidden positions, and visited places.

First, we start at the starting position (0), with step count as 0, and add it to the queue. We also keep track of the visited positions and forbidden positions.

While the queue is not empty, we dequeue the first position, check if it's the house (x), and return the step count if it is. Otherwise, we try to jump to the next positions (current position + a and current position + b) and check if they are valid (within range and not forbidden or visited). If they are valid, we add them to the queue and mark them as visited.

We also need to check if jumping backward (current position - a or current position - b) is allowed. If it is, we need to add them to the queue as well, but we need to mark them as "visited" instead of "forbidden" so that we don't visit them again.

If we exhaust all possible paths and cannot reach the house, we return -1.

Here's the code implementation:

class Solution {
public:
    int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
        unordered_set<int> visited;
        unordered_set<int> forbids(forbidden.begin(), forbidden.end());

        queue<pair<int, int>> q;
        // mark starting position as visited
        visited.insert(0);
        q.push({0, 0}); // position and steps taken, starting as 0

        while (!q.empty()) {
            auto [pos, steps] = q.front();
            q.pop();

            if (pos == x) return steps;

            // try to jump forward
            if (pos + a <= MAX_POS && !forbids.count(pos + a) && !visited.count(pos + a)) {
                visited.insert(pos + a);
                q.push({pos + a, steps + 1});
            }

            if (pos + b <= MAX_POS && !forbids.count(pos + b) && !visited.count(pos + b)) {
                visited.insert(pos + b);
                q.push({pos + b, steps + 1});
            }

            // try to jump backward if allowed
            if (pos - b >= 0 && b < a && !forbids.count(pos - b) && !visited.count(pos - b)) {
                visited.insert(pos - b);
                q.push({pos - b, steps + 1});
            }

            if (q.empty()) break;

            // check if next jump would leave us behind
            auto next_jump = q.front().first;
            if (next_jump + a > MAX_POS && next_jump + b > MAX_POS) break;
        }

        return -1;
    }

private:
    static constexpr int MAX_POS = 2 * 100000 + 1;
};

The time complexity of this solution is O(n), where n is the maximum possible positions we visit (in this case, the double of the maximum coordinate value, since we can only jump forward). The space complexity is also O(n) as we use an unordered set to keep track of visited and forbidden positions.

1