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:
a positions forward (to the right).b positions backward (to the left).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 <= 10001 <= a, b, forbidden[i] <= 20000 <= x <= 2000forbidden are distinct.x is not forbidden.The key idea in #1654 Minimum Jumps to Reach Home is to model the problem as a shortest path search. Each position on the number line represents a state, and from any state you can move +a (forward) or -b (backward). However, some positions are forbidden and two consecutive backward jumps are not allowed, which adds an extra state constraint.
A common strategy is to apply Breadth-First Search (BFS), since we want the minimum number of jumps. During traversal, store both the current position and whether the previous move was backward. This prevents invalid sequences of moves. To avoid infinite exploration to the right, define a reasonable upper bound for positions and maintain a visited structure for forward and backward states.
BFS guarantees that the first time we reach the target position, we have found the minimum number of jumps. With proper pruning of forbidden and visited states, the algorithm remains efficient.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Breadth-First Search with state tracking | O(N) | O(N) |
Greg Hogg
Use these hints if you're stuck. Try solving on your own first.
Think of the line as a graph
to handle the no double back jumps condition you can handle it by holding the state of your previous jump
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, similar BFS and state-space search problems frequently appear in technical interviews at companies like Amazon, Google, and Meta. This problem tests graph traversal, state modeling, and constraint handling.
A queue is the most suitable data structure because BFS requires processing states in order of increasing distance. A visited set or boolean array is also used to avoid revisiting positions with the same movement state.
The optimal approach uses Breadth-First Search (BFS) to explore positions level by level, ensuring the minimum number of jumps. Each state tracks the current position and whether the last jump was backward to prevent consecutive backward moves.
The problem restricts making two consecutive backward jumps. Tracking whether the last move was backward helps enforce this rule and ensures only valid transitions are explored during BFS.