1654. Minimum Jumps to Reach Home LeetCode Solution

In this guide, you will get 1654. Minimum Jumps to Reach Home LeetCode Solution with the best time and space complexity. The solution to Minimum Jumps to Reach Home problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Minimum Jumps to Reach Home solution in C++
Minimum Jumps to Reach Home solution in Java
Minimum Jumps to Reach Home solution in Python
Additional Resources

1654. Minimum Jumps to Reach Home LeetCode Solution image

Problem Statement of Minimum Jumps to Reach Home

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:

It can jump exactly a positions forward (to the right).
It can jump exactly b positions backward (to the left).
It cannot jump backward twice in a row.
It cannot jump to any forbidden positions.

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.

Constraints:

1 <= forbidden.length <= 1000
1 <= a, b, forbidden[i] <= 2000
0 <= x <= 2000
All the elements in forbidden are distinct.
Position x is not forbidden.

Complexity Analysis

Time Complexity: O(\max(x, \max(\texttt{forbidden})) + a + b)
Space Complexity: O(\max(x, \max(\texttt{forbidden})) + a + b)

1654. Minimum Jumps to Reach Home LeetCode Solution in C++

enum class Direction { kForward, kBackward };

class Solution {
 public:
  int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
    int furthest = x + a + b;
    unordered_set<int> seenForward;
    unordered_set<int> seenBackward;

    for (const int pos : forbidden) {
      seenForward.insert(pos);
      seenBackward.insert(pos);
      furthest = max(furthest, pos + a + b);
    }

    // (direction, position)
    queue<pair<Direction, int>> q{{{Direction::kForward, 0}}};

    for (int ans = 0; !q.empty(); ++ans)
      for (int sz = q.size(); sz > 0; --sz) {
        const auto [dir, pos] = q.front();
        q.pop();
        if (pos == x)
          return ans;
        const int forward = pos + a;
        const int backward = pos - b;
        if (forward <= furthest && seenForward.insert(forward).second)
          q.emplace(Direction::kForward, forward);
        // It cannot jump backward twice in a row.
        if (dir == Direction::kForward && backward >= 0 &&
            seenBackward.insert(backward).second)
          q.emplace(Direction::kBackward, backward);
      }

    return -1;
  }
};
/* code provided by PROGIEZ */

1654. Minimum Jumps to Reach Home LeetCode Solution in Java

enum Direction { kForward, kBackward }

class Solution {
  public int minimumJumps(int[] forbidden, int a, int b, int x) {
    int furthest = x + a + b;
    Set<Integer> seenForward = new HashSet<>();
    Set<Integer> seenBackward = new HashSet<>();

    for (final int pos : forbidden) {
      seenForward.add(pos);
      seenBackward.add(pos);
      furthest = Math.max(furthest, pos + a + b);
    }

    // (direction, position)
    Queue<Pair<Direction, Integer>> q =
        new ArrayDeque<>(List.of(new Pair<>(Direction.kForward, 0)));

    for (int ans = 0; !q.isEmpty(); ++ans)
      for (int sz = q.size(); sz > 0; --sz) {
        Direction dir = q.peek().getKey();
        final int pos = q.poll().getValue();
        if (pos == x)
          return ans;
        final int forward = pos + a;
        final int backward = pos - b;
        if (forward <= furthest && seenForward.add(forward))
          q.offer(new Pair<>(Direction.kForward, forward));
        // It cannot jump backward twice in a row.
        if (dir == Direction.kForward && backward >= 0 && seenBackward.add(backward))
          q.offer(new Pair<>(Direction.kBackward, backward));
      }

    return -1;
  }
}
// code provided by PROGIEZ

1654. Minimum Jumps to Reach Home LeetCode Solution in Python

from enum import Enum


class Direction(Enum):
  kForward = 0
  kBackward = 1


class Solution:
  def minimumJumps(self, forbidden: list[int], a: int, b: int, x: int) -> int:
    furthest = max(x + a + b, max(pos + a + b for pos in forbidden))
    seenForward = {pos for pos in forbidden}
    seenBackward = {pos for pos in forbidden}

    # (direction, position)
    q = collections.deque([(Direction.kForward, 0)])

    ans = 0
    while q:
      for _ in range(len(q)):
        dir, pos = q.popleft()
        if pos == x:
          return ans
        forward = pos + a
        backward = pos - b
        if forward <= furthest and forward not in seenForward:
          seenForward.add(forward)
          q.append((Direction.kForward, forward))
        # It cannot jump backward twice in a row.
        if dir == Direction.kForward and backward >= 0 and backward not in seenBackward:
          seenBackward.add(backward)
          q.append((Direction.kBackward, backward))
      ans += 1

    return -1
 # code by PROGIEZ