LeetCode 1654 - Minimum Jumps to Reach Home

LeetCode Problem 1654

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Breadth-First Search

Solution

Problem Understanding

This problem asks us to find the minimum number of jumps required for a bug to move from position 0 to position x on a one dimensional number line.

The bug follows several movement rules:

• It may jump forward by exactly a units.
• It may jump backward by exactly b units.
• It may not perform two consecutive backward jumps.
• It may never land on a forbidden position.
• It may never move to a negative position.

The goal is not simply to determine whether the target is reachable, but to compute the minimum number of jumps needed to reach it.

The input consists of:

• forbidden, an array of blocked positions.
• a, the fixed forward jump distance.
• b, the fixed backward jump distance.
• x, the destination position.

The constraints are relatively small:

• Positions are bounded around 2000.
• At most 1000 forbidden positions exist.

These constraints strongly suggest that a graph traversal approach is feasible. Each reachable position can be treated as a node, and each legal jump can be treated as an edge.

One subtle aspect of the problem is the restriction against consecutive backward jumps. This means the state is not determined solely by the current position. We must also know whether the previous move was backward. Two visits to the same position can represent different valid future possibilities depending on how that position was reached.

Another important detail is that the bug may overshoot the target. A naive implementation that limits movement to positions less than or equal to x would fail on valid cases where moving beyond x is necessary before jumping backward to the target.

Key edge cases include:

• The target may already be unreachable because all useful paths are blocked.
• The optimal path may require overshooting x.
• Revisiting the same position with different previous jump directions must be handled correctly.
• Infinite exploration must be avoided because forward jumps can continue indefinitely.

The problem guarantees that x itself is not forbidden, which simplifies the implementation slightly.

Approaches

Brute Force Approach

A brute force solution would recursively explore every possible sequence of valid jumps starting from position 0.

At each position, the algorithm could:

• Jump forward by a
• Jump backward by b, if the previous move was not backward

The recursion would continue until either:

• The target x is reached
• The path becomes invalid

This approach is correct because it explores all legal jump sequences. However, it is computationally infeasible because the number of possible paths grows exponentially. Without careful pruning, the same states are revisited repeatedly, and forward jumps can continue indefinitely.

Even adding memoization is not enough unless the state includes both:

• Current position
• Whether the previous jump was backward

Additionally, we must impose a maximum exploration boundary to prevent infinite searching.

Optimal Approach, Breadth First Search

The problem naturally maps to an unweighted shortest path problem.

Each valid state consists of:

• The current position
• Whether the previous jump was backward

Each jump costs exactly one move, so Breadth First Search, BFS, guarantees that the first time we reach the target, we have found the minimum number of jumps.

The key insight is that BFS explores states level by level:

• All states reachable in 1 jump
• Then all states reachable in 2 jumps
• And so on

This perfectly matches the requirement to minimize jumps.

We also maintain a visited set containing both:

• Position
• Previous move direction

This prevents revisiting identical states while still allowing revisits to the same position under different movement conditions.

Finally, we establish a practical upper bound for exploration. Since all values are at most 2000, a limit around 6000 safely covers all meaningful reachable states without risking infinite expansion.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	Exponential	Explores all possible jump sequences recursively
Optimal BFS	O(M)	O(M)	BFS over reachable states, where M is the bounded search space

Algorithm Walkthrough

1. Convert the forbidden array into a hash set.

Membership checks happen frequently during traversal. A hash set allows constant time lookup when determining whether a position is blocked. 2. Define the BFS state.

Each state contains:

• Current position
• Whether the previous move was backward

This distinction is necessary because two consecutive backward jumps are forbidden. 3. Choose a safe upper bound.

The search space must be finite. A common safe bound is:

upper_bound = max(x, max(forbidden)) + a + b + 2000

Many implementations simply use 6000, which is sufficient given the constraints. 4. Initialize the BFS queue.

Start from:

• Position 0
• Previous move was not backward
• Jump count 0

5. Initialize the visited set.

Mark (0, False) as visited.

The boolean represents whether the previous move was backward. 6. Process states level by level.

Repeatedly dequeue a state from the BFS queue.

If the current position equals x, return the current jump count. 7. Attempt a forward jump.

Compute:

next_forward = position + a

The forward jump is valid if:

• It does not exceed the upper bound
• It is not forbidden
• The state has not been visited before

Add the new state to the queue with:

• Position next_forward
• Previous move was not backward

8. Attempt a backward jump.

Backward movement is allowed only if the previous move was not backward.

Compute:

next_backward = position - b

The backward jump is valid if:

• The position is non negative
• The position is not forbidden
• The state has not been visited before

Add the new state with:

• Position next_backward
• Previous move was backward

9. Continue until the queue becomes empty.

If BFS finishes without reaching x, return -1.

Why it works

BFS guarantees shortest path discovery in unweighted graphs. Every legal jump corresponds to one edge with equal cost. Since BFS explores all states reachable in k jumps before exploring states reachable in k + 1 jumps, the first time we reach x must represent the minimum number of jumps.

The visited set prevents infinite cycles and redundant exploration, while the additional backward state correctly enforces the rule prohibiting consecutive backward jumps.

Python Solution

from collections import deque
from typing import List

class Solution:
    def minimumJumps(self, forbidden: List[int], a: int, b: int, x: int) -> int:
        forbidden_set = set(forbidden)

        upper_bound = 6000

        queue = deque([(0, False, 0)])
        visited = {(0, False)}

        while queue:
            position, last_backward, jumps = queue.popleft()

            if position == x:
                return jumps

            forward_position = position + a

            if (
                forward_position <= upper_bound
                and forward_position not in forbidden_set
                and (forward_position, False) not in visited
            ):
                visited.add((forward_position, False))
                queue.append((forward_position, False, jumps + 1))

            backward_position = position - b

            if (
                not last_backward
                and backward_position >= 0
                and backward_position not in forbidden_set
                and (backward_position, True) not in visited
            ):
                visited.add((backward_position, True))
                queue.append((backward_position, True, jumps + 1))

        return -1

The implementation begins by converting the forbidden positions into a set for efficient lookup.

The BFS queue stores tuples containing:

• Current position
• Whether the previous move was backward
• Number of jumps taken so far

The visited set also stores both position and backward state. This is essential because reaching the same position under different movement conditions produces different future possibilities.

Inside the BFS loop, the algorithm first checks whether the current position equals the target.

The forward jump is always considered. If valid, it is added to the queue with last_backward = False.

The backward jump is considered only when the previous move was not backward. This directly enforces the problem constraint against consecutive backward jumps.

If BFS exhausts all reachable states without reaching the target, the function returns -1.

Go Solution

package main

import "container/list"

type State struct {
	position     int
	lastBackward bool
	jumps        int
}

type VisitState struct {
	position     int
	lastBackward bool
}

func minimumJumps(forbidden []int, a int, b int, x int) int {
	forbiddenSet := make(map[int]bool)

	for _, pos := range forbidden {
		forbiddenSet[pos] = true
	}

	upperBound := 6000

	queue := list.New()
	queue.PushBack(State{0, false, 0})

	visited := make(map[VisitState]bool)
	visited[VisitState{0, false}] = true

	for queue.Len() > 0 {
		front := queue.Front()
		queue.Remove(front)

		current := front.Value.(State)

		position := current.position
		lastBackward := current.lastBackward
		jumps := current.jumps

		if position == x {
			return jumps
		}

		forwardPosition := position + a

		for forwardPosition <= upperBound &&
			!forbiddenSet[forwardPosition] &&
			!visited[VisitState{forwardPosition, false}] {

			visited[VisitState{forwardPosition, false}] = true
			queue.PushBack(State{forwardPosition, false, jumps + 1})
			break
		}

		backwardPosition := position - b

		if !lastBackward &&
			backwardPosition >= 0 &&
			!forbiddenSet[backwardPosition] &&
			!visited[VisitState{backwardPosition, true}] {

			visited[VisitState{backwardPosition, true}] = true
			queue.PushBack(State{backwardPosition, true, jumps + 1})
		}
	}

	return -1
}

The Go solution follows the same BFS logic as the Python implementation.

Since Go does not provide a built in deque structure equivalent to Python's collections.deque, the implementation uses container/list as the queue.

Custom structs are used for:

• BFS state storage
• Visited state tracking

Go maps are used to simulate hash sets for forbidden positions and visited states.

Unlike Python tuples, Go requires explicit struct definitions to represent composite keys in hash maps.

Worked Examples

Example 1

forbidden = [14,4,18,1,15]
a = 3
b = 15
x = 9

Initial state:

Queue	Visited
(0, False, 0)	(0, False)

Process (0, False, 0):

• Forward: 3
• Backward: -15 invalid

Queue
(3, False, 1)

Process (3, False, 1):

• Forward: 6
• Backward: -12 invalid

Queue
(6, False, 2)

Process (6, False, 2):

• Forward: 9
• Backward: -9 invalid

Queue
(9, False, 3)

Process (9, False, 3):

Target reached.

Answer: 3

Example 2

forbidden = [8,3,16,6,12,20]
a = 15
b = 13
x = 11

Start from 0.

Possible forward jumps create positions such as:

0 -> 15 -> 30 -> ...

Backward moves generate positions like:

15 -> 2
30 -> 17

However, forbidden positions and movement constraints eventually block all reachable paths.

BFS exhausts the search space without reaching 11.

Answer: -1

Example 3

forbidden = [1,6,2,14,5,17,4]
a = 16
b = 9
x = 7

Initial queue:

Position	Last Backward	Jumps
0	False	0

From 0:

• Forward to 16

Queue:

Position	Last Backward	Jumps
16	False	1

From 16:

• Forward to 32
• Backward to 7

Queue:

Position	Last Backward	Jumps
32	False	2
7	True	2

Processing 7 reaches the target.

Answer: 2

Complexity Analysis

Measure	Complexity	Explanation
Time	O(M)	Each state is processed at most once
Space	O(M)	Queue and visited set store reachable states

Here, M represents the bounded search space. Since positions are capped by a fixed upper bound around 6000, the actual runtime remains small.

Each position may appear twice in the visited structure:

• Once after a forward move
• Once after a backward move

Therefore, the total number of states is linear in the bounded range.

Test Cases

solution = Solution()

# Provided examples
assert solution.minimumJumps([14,4,18,1,15], 3, 15, 9) == 3  # simple forward path
assert solution.minimumJumps([8,3,16,6,12,20], 15, 13, 11) == -1  # unreachable target
assert solution.minimumJumps([1,6,2,14,5,17,4], 16, 9, 7) == 2  # overshoot then backward

# Target already at start
assert solution.minimumJumps([], 3, 2, 0) == 0  # no jumps needed

# Single forward jump
assert solution.minimumJumps([], 4, 2, 4) == 1  # direct forward jump

# Requires avoiding forbidden positions
assert solution.minimumJumps([2,4,6], 3, 1, 7) == 4  # navigate around blocked cells

# Impossible because all paths blocked
assert solution.minimumJumps([1,2,3,4], 2, 1, 5) == -1  # cannot progress

# Requires revisiting positions with different states
assert solution.minimumJumps([10], 6, 4, 8) == 3  # state distinction matters

# Large target with overshoot
assert solution.minimumJumps([], 5, 3, 17) == 5  # overshooting allowed

# Forbidden near target
assert solution.minimumJumps([9], 3, 2, 11) != -1  # alternative route exists

Test	Why
Example 1	Validates straightforward BFS traversal
Example 2	Confirms unreachable targets return -1
Example 3	Verifies overshooting and backward movement
x = 0	Tests immediate success case
Single forward jump	Tests simplest nontrivial path
Forbidden positions	Ensures blocked cells are skipped
Fully blocked paths	Confirms BFS termination correctness
Revisiting states	Verifies state includes backward flag
Large overshoot	Tests movement beyond target
Forbidden near target	Ensures alternate routing works

Edge Cases

One important edge case occurs when the target is 0. Since the bug already starts at position 0, the answer should immediately be 0 without performing any BFS expansion. The implementation naturally handles this because the initial queue state is checked against the target before generating new moves.

Another tricky edge case involves overshooting the target. A naive solution might restrict exploration to positions less than or equal to x, but valid paths sometimes require moving past the destination and then jumping backward. The implementation avoids this bug by allowing exploration up to a safe upper bound rather than stopping at the target.

A particularly subtle edge case arises from the restriction against consecutive backward jumps. Suppose a position is reached after a backward move. Future backward moves from that state are forbidden. If the visited structure tracked only positions, the algorithm could incorrectly prune valid paths. The implementation solves this by storing both the position and whether the previous move was backward.

Another important scenario involves infinite exploration. Since forward jumps can continue indefinitely, BFS without a boundary would never terminate in some unreachable cases. The implementation uses a fixed upper bound of 6000, which is sufficient under the given constraints and guarantees termination.