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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Breadth-First Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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
apositions forward (to the right), or - exactly
bpositions 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 <= 10001 <= a, b, forbidden[i] <= 20000 <= x <= 2000all values in forbidden are distinctx is not forbidden
Hints for Minimum Jumps to Reach Home
Hint 1
Every jump costs one, so BFS finds the fewest jumps — but the state must also remember whether the previous jump went backward.
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.
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
- Put the forbidden positions in a set and compute
limit = max(x, max(forbidden)) + a + b. - BFS from
(0, false)with distance 0. - From
(p, back): the forward jump top + ais allowed if it is withinlimitand not forbidden; the backward jump top − bis allowed ifbackis false and the target is non-negative and not forbidden. - 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
xis 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 -1Java
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