1654. Minimum Jumps to Reach Home

MediumBreadth-First SearchArrayDynamic Programming

Problem Description

In this problem, we have to find the minimum number of jumps a bug needs to take to get from position 0 to its home at a specified position x on the x-axis. The bug has specific rules for jumping; it can jump forward by a positions, or backward by b positions, but cannot jump backward twice in a row. Additionally, there are forbidden positions the bug cannot land on, provided in an array forbidden. The goal is to calculate the fewest jumps required for the bug to reach position x. If the bug cannot reach its home following the jump rules and avoiding forbidden positions, we should return -1.

Intuition

The problem can be approached using the Breadth-First Search (BFS) algorithm. The idea behind using BFS here is that it can help us traverse the possible positions level by level, starting from 0, with each level representing a jump, until we reach the desired position x. This approach ensures that we get the minimum number of jumps because we visit nodes in order of their distance from the starting point.

To implement BFS, we typically use a queue to keep track of the positions we need to visit and the direction of the last jump (forward or backward). We also use a set to keep track of the forbidden positions, and another set to record visited positions along with the direction (this is important to avoid repeat visits to the same spot with the same last jump direction).

The thought process includes the following considerations:

We treat each position and its last jump direction as a state (position, direction), where direction can be 1 for a forward jump and 0 for a backward jump.
The queue is initialized with the starting state (0, 1), meaning the bug starts at position 0 and can jump in either direction.
A loop is used to process all states in the queue, where for each state:
- If the current position is x, we can return the current number of jumps (the level number in BFS terms).
- We generate possible next states from the current state, one for jumping forward and, if it's allowed, one for jumping backward.
- For each next state, if the new position is non-negative, not forbidden, not already visited, and less than a certain threshold (6000 in this case, set to prevent infinite searching where the bug keeps jumping forward and backward), we add it to the queue for the next level.
If none of the states in the queue lead us to the position x, and there are no more states to consider, we return -1, as it's impossible to reach the bug's home.

Through BFS, we guarantee we're exploring the shortest path first, and once we reach the home, we immediately have the minimum number of jumps that it took to get there.

Learn more about Breadth-First Search and Dynamic Programming patterns.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece：

What's the relationship between a tree and a graph?

A graph is a special treeA tree is a special graphNo relationshipThey are the same thing

I don’t know

Solution Approach

The solution uses the Breadth-First Search algorithm (BFS) to explore positions the bug can jump to. The algorithm uses the following data structures and concepts:

Queue: A deque is used to implement the queue functionality needed for BFS. It stores tuples in the form (position, direction), where 'position' is the current position of the bug and 'direction' is a binary flag indicating the last jump (1 for forward and 0 for backward).
Set: Two sets are used:
- One set s to store the forbidden positions which the bug should not jump to.
- Another set vis (visited) to store positions along with the last jump's direction the bug has already been to in order to prevent revisiting the same states.
Loop: The code iterates over each level of the queue until it is empty or the home position x is found. This represents a single jump made by the bug.

Here’s a breakdown of how the code works:

Initialize a set s with forbidden positions to efficiently check if a given position is forbidden in O(1) time.
Start the BFS from position 0 with a direction of 1 (forward), indicating that the bug can jump in any direction from the start.
Use a while loop to process all positions in the queue:
- For each position in the queue at the current level (ans), there can be two possible actions: jump forward or jump backward (if not already taken as the last action).
- Create a nxt list to hold possible next states.
- Add a state for moving forward (position + a).
- If the last jump was not backward (checked by if k & 1:), also add a state for moving backward (position - b).
For each of the next states:
- Check if the new position is non-negative, not forbidden, and not yet visited. There is also a threshold of 6000 to limit the space—positions beyond this are not considered.
- If all conditions are met, add the new state (j, k) to the queue to explore in the next level and mark it as visited in the vis set.
Increment the counter ans after each level is processed, which represents the number of jumps made.
If at any point the current position i is the home position x, return the current jump counter ans as the minimum number of jumps needed.

If the queue is exhausted and the home position x has not been reached, return -1, indicating that it is impossible for the bug to reach its home.

This BFS approach ensures that the shortest path to position x is found first, accounting for forbidden positions and jump rules, thus providing the correct minimum number of jumps required.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

Consider the classic dynamic programming of fibonacci numbers, what is the recurrence relation?

dp[i] = dp[i - 1] + dp[i - 2]dp[i] = dp[i - 1] + 1dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3]dp[i] = dp[i - 1]

I don’t know

Example Walkthrough

Let's consider a small example to illustrate the solution approach with the following parameters:

Position x (home) is at 10.
The bug jumps forward by a = 6 and backward by b = 4.
Forbidden positions are given by the array forbidden = [14].

Initial Setup

Create a set s with the forbidden positions: s = {14}.
Initialize the starting state in the queue deque as (0, 1), meaning the bug is at position 0 and the last jump was forward (arbitrarily since the bug is at start), and initialize ans = 0 which will keep count of the jumps.

BFS Traversal

The queue initially contains one state: (0, 1). This is the initial position with a forward jump.

First Jump

Dequeue the first state (0, 1). From this state, the bug can either jump to position 0 + 6 = 6 or position 0 - 4, but it will not jump backward since that would result in a negative position.
Check if position 6 is forbidden or not (6 not in s) and not visited (not in vis). Since it's not forbidden and not visited, enqueue (6, 1) into the queue and add it to the set vis.
Increment ans to 1.

Continue BFS

Dequeue (6, 1). Now, the bug can jump to position 12 by moving forward or 2 by moving backward. Position 12 is not forbidden but is beyond the target 10, so we skip it as it's not efficient. Position 2 is not forbidden and not visited, therefore, enqueue (2, 0) into the queue and add it to vis.
Increment ans to 2.

Check for Home Position

Dequeue (2, 0). The bug can jump to 8 (moving forward) or 2 - 4 = -2 (moving backward), but backward is not allowed since it was the last jump direction.
The jump to 8 does not violate any constraints (forbidden, visited, or threshold). Add (8, 1) to the queue and vis.
Increment ans to 3.

Home Found

Dequeue (8, 1). The bug can now jump to 14 (forward) or 4 (backward). We skip 14 as it's forbidden, but 4 is not.
Now the bug can jump from 4 to 10 with a forward jump. We check if 10 is forbidden or visited. It's neither, and 10 is our target home position.
Return the current jump counter ans, which is 4. This implies that the minimum number of jumps needed for the bug to reach its home at position 10 is 4.

If Home Not Found

If the bug had not found the home at any point, and all possible jumps had either been processed or discarded due to constraints, we would simply exit the loop and return -1.

The above steps demonstrate through a simple example how a BFS approach is used to find the minimum number of jumps required for the bug to reach home while avoiding forbidden positions and not jumping backward twice in a row.

Solution Implementation

1from collections import deque
2
3class Solution:
4    def minimumJumps(self, forbidden: List[int], forward_step: int, backward_step: int, target: int) -> int:
5        # Initialize a set of forbidden positions
6        forbidden_set = set(forbidden)
7      
8        # Queue for breadth-first search with position and whether the last movement was forward (1) or backward (0)
9        queue = deque([(0, 1)])
10      
11        # Visited set to keep track of positions and their last movement direction
12        visited = {(0, 1)}
13      
14        # Step counter starting from 0
15        steps = 0
16      
17        # Start breadth-first search
18        while queue:
19            # Process nodes level by level
20            for _ in range(len(queue)):
21                position, last_movement_forward = queue.popleft()
22              
23                # If the current position is the target, return the number of steps
24                if position == target:
25                    return steps
26              
27                # List of possible next positions
28                next_positions = [(position + forward_step, 1)]  # always can go forward
29              
30                # Can only go backward if the last movement was forward
31                if last_movement_forward:
32                    next_positions.append((position - backward_step, 0))
33              
34                # Iterate over possible next positions
35                for next_position, next_movement_forward in next_positions:
36                    # Check if within bounds, not forbidden, and not already visited
37                    if (0 <= next_position < 6000 and 
38                        next_position not in forbidden_set and 
39                        (next_position, next_movement_forward) not in visited):
40                      
41                        # Add to queue and mark as visited
42                        queue.append((next_position, next_movement_forward))
43                        visited.add((next_position, next_movement_forward))
44          
45            # Increment steps after finishing processing the current level
46            steps += 1
47      
48        # Return -1 if it's not possible to reach the target
49        return -1
50

1class Solution {
2    public int minimumJumps(int[] forbidden, int forwardJump, int backwardJump, int target) {
3        // Create a hash set to store forbidden positions for fast access
4        Set<Integer> forbiddenSet = new HashSet<>();
5        for (int position : forbidden) {
6            forbiddenSet.add(position);
7        }
8      
9        // Declare a deque to perform BFS
10        Deque<int[]> queue = new ArrayDeque<>();
11        queue.offer(new int[] {0, 1}); // Starting at position 0; 1 indicates next jump can be either forward or backward
12      
13        // Define upper bound of positions to avoid infinite searching
14        final int MAX_POSITION = 6000;
15      
16        // Create a visited matrix to track visited positions; two states for forward [][1] or backward [][0] jump
17        boolean[][] visited = new boolean[MAX_POSITION][2];
18        visited[0][1] = true; // We start at position 0 and can move either forward or backward
19      
20        // BFS to find minimum jumps to reach the target
21        for (int steps = 0; !queue.isEmpty(); ++steps) {
22            // Process nodes that are at the same level
23            for (int size = queue.size(); size > 0; --size) {
24                int[] currentPosition = queue.poll();
25                int position = currentPosition[0];
26                int canJumpBackward = currentPosition[1];
27              
28                // If current position is the target, return the number of steps taken
29                if (position == target) {
30                    return steps;
31                }
32              
33                // Store next positions from current position
34                List<int[]> nextPositions = new ArrayList<>();
35                nextPositions.add(new int[] {position + forwardJump, 1}); // Always can jump forward
36              
37                // Check if we can jump backward from the current position
38                if (canJumpBackward == 1) {
39                    nextPositions.add(new int[] {position - backwardJump, 0}); // After jumping back, can't jump back again right away
40                }
41              
42                // Explore next positions
43                for (int[] nextPos : nextPositions) {
44                    int newPosition = nextPos[0];
45                    int newCanJumpBackward = nextPos[1];
46                  
47                    // Validate new position (not forbidden, within bounds, and not visited)
48                    if (newPosition >= 0 &&
49                        newPosition < MAX_POSITION &&
50                        !forbiddenSet.contains(newPosition) &&
51                        !visited[newPosition][newCanJumpBackward]) {
52                      
53                        // Add valid position to the queue and mark it as visited
54                        queue.offer(new int[] {newPosition, newCanJumpBackward});
55                        visited[newPosition][newCanJumpBackward] = true;
56                    }
57                }
58            }
59        }
60      
61        // If we exhaust the queue without reaching the target, return -1 indicating it's impossible
62        return -1;
63    }
64}
65

1#include <vector>
2#include <unordered_set>
3#include <queue>
4#include <cstring>
5
6class Solution {
7public:
8    int minimumJumps(std::vector<int>& forbidden, int forwardJump, int backwardJump, int target) {
9        // Transform the forbidden list into a set for fast lookup.
10        std::unordered_set<int> forbiddenSet(forbidden.begin(), forbidden.end());
11
12        // Queue to hold the current position and jump direction (1 for forward, 0 for backward).
13        std::queue<std::pair<int, int>> queue;
14        queue.emplace(0, 1); // Start with position 0 and direction forward.
15
16        // Define the maximum possible position to consider, to avoid infinite searching.
17        const int MAX_POSITION = 6000;
18
19        // Visited positions array to keep track of places already visited and direction used.
20        bool visited[MAX_POSITION][2];
21
22        // Initialize the visited array to false.
23        std::memset(visited, false, sizeof(visited));
24        visited[0][1] = true; // Mark the start (0, forward) as visited.
25
26        // Variable to track the number of jumps.
27        int jumpCount = 0;
28
29        // BFS algorithm to find the minimum number of jumps to reach the target.
30        while (!queue.empty()) {
31            for (int levelSize = queue.size(); levelSize > 0; --levelSize) {
32                auto [currentPosition, canJumpBackward] = queue.front();
33                queue.pop();
34
35                // If the target position is reached, return the number of jumps.
36                if (currentPosition == target) {
37                    return jumpCount;
38                }
39
40                // Calculate the next forward position.
41                int nextForwardPosition = currentPosition + forwardJump;
42
43                // Consider the next positions to move (forward and maybe backward).
44                std::vector<std::pair<int, int>> nextPositions = {{nextForwardPosition, 1}};
45                if (canJumpBackward) {
46                    int nextBackwardPosition = currentPosition - backwardJump;
47                    nextPositions.emplace_back(nextBackwardPosition, 0);
48                }
49
50                // Process each valid next position.
51                for (auto [nextPosition, nextDirection] : nextPositions) {
52                    // Check if the next position is within bounds, not forbidden, and not visited.
53                    if (nextPosition >= 0 && nextPosition < MAX_POSITION && !forbiddenSet.count(nextPosition) && !visited[nextPosition][nextDirection]) {
54                        visited[nextPosition][nextDirection] = true; // Mark the next position as visited.
55                        queue.emplace(nextPosition, nextDirection); // Add to queue for further exploration.
56                    }
57                }
58            }
59            jumpCount++; // Increase the jump count for the next level.
60        }
61
62        // If we exited the loop, there is no way to reach the target.
63        return -1;
64    }
65};
66

1function minimumJumps(forbidden: number[], forwardStep: number, backwardStep: number, target: number): number {
2  // A set to hold forbidden positions for quick access.
3  const forbiddenPositions: Set<number> = new Set(forbidden);
4
5  // Initialize a queue to perform BFS with a tuple containing position and the direction flag (forward = 1, backward = 0).
6  const queue: [number, number][] = [[0, 1]];
7
8  // Define a boundary since the problem allows for a finite search space.
9  const maxPosition = 6000;
10
11  // Visited array to keep track of positions already checked.
12  // vis[position][direction] indicates whether the position has been visited in a particular direction.
13  const visited: boolean[][] = Array.from({ length: maxPosition }, () => [false, false]);
14
15  // Mark the start position [0,1] as visited.
16  visited[0][1] = true;
17
18  // Start the BFS.
19  for (let steps = 0; queue.length; ++steps) {
20    for (let size = queue.length; size > 0; --size) {
21      // Dequeue the next position and direction.
22      const [position, direction] = queue.shift()!;
23
24      // If target is reached, return the number of steps taken.
25      if (position === target) {
26        return steps;
27      }
28
29      // Calculate the next positions to visit.
30      const nextPositions: [number, number][] = [[position + forwardStep, 1]];
31
32      // If the last step was forward, we can go backward.
33      if (direction === 1) {
34        nextPositions.push([position - backwardStep, 0]);
35      }
36
37      // Check the next possible positions.
38      for (const [nextPosition, nextDirection] of nextPositions) {
39        // Check that the position is within bounds, not forbidden, and not visited yet in that direction.
40        if (nextPosition >= 0 && nextPosition < maxPosition &&
41            !forbiddenPositions.has(nextPosition) && !visited[nextPosition][nextDirection]) {
42          // Mark the position as visited in the current direction.
43          visited[nextPosition][nextDirection] = true;
44
45          // Enqueue the position for further exploration.
46          queue.push([nextPosition, nextDirection]);
47        }
48      }
49    }
50  }
51
52  // If the target is not reachable, return -1.
53  return -1;
54}
55

Not Sure What to Study? Take the 2-min Quiz：

What is an advantages of top-down dynamic programming vs bottom-up dynamic programming?

It's fasterIt has better space complexityOrder of computer subproblems does not matterIt has better time complexity

I don’t know

Time and Space Complexity

The time complexity of the code is O(N + a + b), where N is the maximum position that can be reached considering the constraints of the problem. Since the algorithm uses a breadth-first search and each position is visited at most once, the time complexity is linear in terms of the number of positions checked. The factor of a + b comes from the maximum range we might need to explore to ensure we can reach position x or determine it's impossible. In the worst case, the algorithm explores up to position x + b (since jumping b back from beyond x is the furthest we would need to go) and the positions backwards until reaching 0. Given the constraint on i (which is that 0 <= i < 6000), N effectively becomes 6000, and thus the time complexity simplifies to O(6000) which is constant, so effectively O(1).

The space complexity of the code is O(N), where N again represents the maximum range of positions considered, which is determined to be 6000 based on the limitations placed within the code (0 <= j < 6000). The space complexity arises from the storage of the vis set containing tuples (position, direction) which tracks the visited positions and the direction from which they were reached. The queue q will also store at most O(N) elements as it holds the positions to be explored. Therefore, space complexity also reduces to O(1) since 6000 is the upper bound regardless of the input size.

Learn more about how to find time and space complexity quickly using problem constraints.

Fast Track Your Learning with Our Quick Skills Quiz:

What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.

Linear SearchBinary SearchQuick SelectHash Set

I don’t know

Overview

Basic Data Structures

Basic Algorithms

Overview

Sorted Array

Implicitly Sorted Array

Advanced

Speedrun

Introduction

DFS on Tree

Binary Search Tree

Advanced

Combinatorial Search

Pruning

Additional States

Aggregation and Memoization

Dedup

Additional Practices

Speedrun

Introduction

BFS on Tree

Introduction

Vanilla BFS

Matrix as Graph

Implicit Graph

Directed Graph / Topological Sort

Weighted Graph

Minimum Spanning Tree

Speedrun

Introduction

Same Direction

Opposite Direction

Sliding Window

Prefix Sum

Cycle Finding

Advanced

Speedrun

Introduction

Top K

Moving Best

Multiple Heaps

Introduction

Grid

Dynamic number of subproblems

Interval

Dual-Sequence

Knapsack

Bitmask

Additional Practices

Disjoint Set Union | Union Find

Trie

Data Structure Design

Segment Tree

Interval

Monotonic Stack

Divide and Conquer

Line Sweep

Tree Traversal without Recursion

Greedy

Math

Matrix

Classics

Concepts

Projects

Amazon OA

Microsoft OA

Google OA

Twitter OA

Editorials

1654. Minimum Jumps to Reach Home

Problem Description

Intuition

Solution Approach

Example Walkthrough

Initial Setup

BFS Traversal

First Jump

Continue BFS

Check for Home Position

Home Found