Minimum Jumps to Reach Home

Medium
1542.

Minimum Jumps to Reach Home

Minimum Jumps to Reach Home is a medium coding problem on arrays, dynamic programming and breadth-first search, asked in Amazon and Google interviews.

A bug starts at position 0 on the x-axis and wants to reach its home at position x. Each jump is one of:

  • exactly a positions forward (to the right), or
  • exactly b positions backward (to the left).

The bug may not jump backward twice in a row, may never land on a negative position, and may never land on any position listed in forbidden. It may jump past its home.

Return the minimum number of jumps needed to land exactly on x, or -1 if it is impossible.

Example 1

Input
forbidden = [1,2,3], a = 4, b = 3, x = 5
Output
3
Explanation
0 → 4 → 8 → 5: two jumps forward, one back.

Example 2

Input
forbidden = [5,9,2], a = 4, b = 3, x = 6
Output
-1
Explanation
Position 6 can only be entered from 2 or 9, and both are forbidden.

Example 3

Input
forbidden = [8], a = 3, b = 2, x = 0
Output
0

Constraints

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • all values in forbidden are distinct
  • x is not forbidden
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} forbidden
 * @param {number} a
 * @param {number} b
 * @param {number} x
 * @return {number}
 */
var minimumJumps = function(forbidden, a, b, x) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Jumps to Reach Home — Solution in Python, Java & C++

Minimum Jumps to Reach Home solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Minimum Jumps to Reach Home is a medium coding problem on arrays, dynamic programming and breadth-first search, asked in Amazon and Google interviews.

Problem statement

A bug starts at position 0 on the x-axis and wants to reach its home at position x. Each jump is one of:

  • exactly a positions forward (to the right), or
  • exactly b positions backward (to the left).

The bug may not jump backward twice in a row, may never land on a negative position, and may never land on any position listed in forbidden. It may jump past its home.

Return the minimum number of jumps needed to land exactly on x, or -1 if it is impossible.

Example 1

Input: forbidden = [1,2,3], a = 4, b = 3, x = 5
Output: 3
Explanation: 0 → 4 → 8 → 5: two jumps forward, one back.

Example 2

Input: forbidden = [5,9,2], a = 4, b = 3, x = 6
Output: -1
Explanation: Position 6 can only be entered from 2 or 9, and both are forbidden.

Example 3

Input: forbidden = [8], a = 3, b = 2, x = 0
Output: 0

Constraints

  • 1 <= forbidden.length <= 1000
  • 1 <= a, b, forbidden[i] <= 2000
  • 0 <= x <= 2000
  • all values in forbidden are distinct
  • x is not forbidden

Hints for Minimum Jumps to Reach Home

  1. Hint 1

    Every jump costs one, so BFS finds the fewest jumps — but the state must also remember whether the previous jump went backward.

  2. Hint 2

    The search space looks infinite to the right. It is enough to explore positions up to max(x, max(forbidden)) + a + b; beyond that, going further right never helps.

  3. Hint 3

    BFS over states (position, lastWasBackward) within that bound, marking each state visited once.

How to solve Minimum Jumps to Reach Home

Breadth-first search over states (position, previous jump was backward), with positions capped at max(x, max(forbidden)) + a + b.

Approach

  1. Put the forbidden positions in a set and compute limit = max(x, max(forbidden)) + a + b.
  2. BFS from (0, false) with distance 0.
  3. From (p, back): the forward jump to p + a is allowed if it is within limit and not forbidden; the backward jump to p − b is allowed if back is false and the target is non-negative and not forbidden.
  4. Return the distance of the first state whose position equals x; if the queue empties, return -1.

Why it works

The rule about consecutive backward jumps depends only on the last move, so the pair (position, last move) captures everything that matters and BFS gives shortest jump counts. The cap is safe: past every forbidden cell and past x, the axis is free, and a shortest route never needs to stray more than one forward and one backward jump beyond the largest of x and the forbidden positions (a known bound for this problem); within the cap the state space is finite, so BFS terminates.

Complexity

  • Time — O(max(x, max(forbidden)) + a + b)
  • Space — O(max(x, max(forbidden)) + a + b)

Pitfalls

  • Visiting a position after a backward jump is a different state from visiting it after a forward jump — keep two visited flags per position.
  • Two backward jumps in a row are illegal even if both targets are free.
  • Without an upper bound the forward jumps run forever when x is unreachable.

Reference solution

Python

from typing import List
from collections import deque

def minimumJumps(forbidden: List[int], a: int, b: int, x: int) -> int:
    limit = max(x, max(forbidden)) + a + b
    blocked = set(forbidden)
    seen = [[False, False] for _ in range(limit + 1)]
    seen[0][0] = True
    q = deque([(0, 0, 0)])
    while q:
        pos, back, steps = q.popleft()
        if pos == x:
            return steps
        nxt = pos + a
        if nxt <= limit and nxt not in blocked and not seen[nxt][0]:
            seen[nxt][0] = True
            q.append((nxt, 0, steps + 1))
        if back == 0:
            nxt = pos - b
            if nxt >= 0 and nxt not in blocked and not seen[nxt][1]:
                seen[nxt][1] = True
                q.append((nxt, 1, steps + 1))
    return -1

Java

public static int minimumJumps(int[] forbidden, int a, int b, int x) {
    int top = x;
    for (int f : forbidden) top = Math.max(top, f);
    int limit = top + a + b;
    boolean[] blocked = new boolean[limit + 1];
    for (int f : forbidden) blocked[f] = true;
    boolean[][] seen = new boolean[limit + 1][2];
    int cap = 2 * (limit + 1) + 1;
    int[] qp = new int[cap], qb = new int[cap], qs = new int[cap];
    int head = 0, tail = 0;
    qp[tail] = 0; qb[tail] = 0; qs[tail++] = 0;
    seen[0][0] = true;
    while (head < tail) {
        int pos = qp[head], back = qb[head], steps = qs[head];
        head++;
        if (pos == x) return steps;
        int fwd = pos + a;
        if (fwd <= limit && !blocked[fwd] && !seen[fwd][0]) {
            seen[fwd][0] = true;
            qp[tail] = fwd; qb[tail] = 0; qs[tail++] = steps + 1;
        }
        int bwd = pos - b;
        if (back == 0 && bwd >= 0 && !blocked[bwd] && !seen[bwd][1]) {
            seen[bwd][1] = true;
            qp[tail] = bwd; qb[tail] = 1; qs[tail++] = steps + 1;
        }
    }
    return -1;
}

C++

int minimumJumps(vector<int>& forbidden, int a, int b, int x) {
    int top = x;
    for (int f : forbidden) top = max(top, f);
    int limit = top + a + b;
    vector<char> blocked(limit + 1, 0), seen(2 * (limit + 1), 0);
    for (int f : forbidden) blocked[f] = 1;
    vector<int> qp, qb, qs;
    qp.push_back(0); qb.push_back(0); qs.push_back(0);
    seen[0] = 1;
    for (size_t h = 0; h < qp.size(); h++) {
        int pos = qp[h], back = qb[h], steps = qs[h];
        if (pos == x) return steps;
        int fwd = pos + a;
        if (fwd <= limit && !blocked[fwd] && !seen[2 * fwd]) {
            seen[2 * fwd] = 1;
            qp.push_back(fwd); qb.push_back(0); qs.push_back(steps + 1);
        }
        int bwd = pos - b;
        if (back == 0 && bwd >= 0 && !blocked[bwd] && !seen[2 * bwd + 1]) {
            seen[2 * bwd + 1] = 1;
            qp.push_back(bwd); qb.push_back(1); qs.push_back(steps + 1);
        }
    }
    return -1;
}

JavaScript

var minimumJumps = function(forbidden, a, b, x) {
    var top = x;
    for (var i = 0; i < forbidden.length; i++) if (forbidden[i] > top) top = forbidden[i];
    var limit = top + a + b;
    var blocked = [], seen = [];
    for (var k = 0; k <= limit; k++) blocked.push(false);
    for (var f = 0; f < forbidden.length; f++) blocked[forbidden[f]] = true;
    for (var s = 0; s < 2 * (limit + 1); s++) seen.push(false);
    var qp = [0], qb = [0], qs = [0];
    seen[0] = true;
    for (var h = 0; h < qp.length; h++) {
        var pos = qp[h], back = qb[h], steps = qs[h];
        if (pos === x) return steps;
        var fwd = pos + a;
        if (fwd <= limit && !blocked[fwd] && !seen[2 * fwd]) {
            seen[2 * fwd] = true;
            qp.push(fwd); qb.push(0); qs.push(steps + 1);
        }
        var bwd = pos - b;
        if (back === 0 && bwd >= 0 && !blocked[bwd] && !seen[2 * bwd + 1]) {
            seen[2 * bwd + 1] = true;
            qp.push(bwd); qb.push(1); qs.push(steps + 1);
        }
    }
    return -1;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming