Skip to content

1654. Minimum Jumps to Reach Home 👍

  • Time: $O(\max(x, \max(\texttt{forbidden})) + a + b)$
  • Space: $O(\max(x, \max(\texttt{forbidden})) + a + b)$
 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
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;
  }
};

 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
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;
  }
}

 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
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