LeetCode 1654: Minimum Jumps to Reach Home
Problem Description
Explanation:
To solve this problem, we can use a breadth-first search (BFS) approach. We will start from position 0 and explore all possible valid moves the bug can make. We will keep track of the visited positions and the number of jumps required to reach each position. If the bug reaches the home position x, we return the number of jumps required. If it is not possible to reach x, we return -1.
Algorithm:
- Initialize a queue for BFS and a set to track visited positions.
- Perform BFS starting from position 0 with 0 jumps.
- At each step, consider two possible moves: a jump forward and a jump backward.
- Check if the new positions are valid and not in the forbidden set.
- If the bug reaches position x, return the number of jumps.
- If the queue is empty and x is not reached, return -1.
Time Complexity:
The time complexity of this algorithm is O(max(x, max(forbidden))).
Space Complexity:
The space complexity of this algorithm is O(max(x, max(forbidden))).
Solutions
class Solution {
public int minimumJumps(int[] forbidden, int a, int b, int x) {
Set<Integer> visited = new HashSet<>();
Set<Integer> forbiddenSet = new HashSet<>();
for (int f : forbidden) {
forbiddenSet.add(f);
}
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{0, 0});
visited.add(0);
int maxPos = x + 2 * a + b;
while (!queue.isEmpty()) {
int[] current = queue.poll();
int pos = current[0];
int jumps = current[1];
if (pos == x) {
return jumps;
}
if (pos + a < maxPos && !forbiddenSet.contains(pos + a) && visited.add(pos + a)) {
queue.offer(new int[]{pos + a, jumps + 1});
}
if (pos - b >= 0 && pos - b != a && !forbiddenSet.contains(pos - b) && visited.add(pos - b)) {
queue.offer(new int[]{pos - b, jumps + 1});
}
}
return -1;
}
}Loading editor...