Leetcode Problem 1654. Minimum Jumps to Reach Home

1654. Minimum Jumps to Reach Home

Leetcode Solutions

Breadth-First Search (BFS) with Backward Jump Check

  1. Initialize a queue to store tuples of the current position, the number of jumps taken, and a boolean indicating if the last jump was backward.
  2. Initialize sets for forbidden positions and visited positions.
  3. Add the starting position 0 to the queue with 0 jumps and mark it as not having a backward jump.
  4. While the queue is not empty, perform the following steps: a. Dequeue the current position, jump count, and backward jump flag. b. If the current position is x, return the jump count as the result. c. Calculate the next forward and backward positions. d. If the forward position is not forbidden, not visited, and within the maximum boundary, enqueue it and mark it as visited. e. If the backward position is not forbidden, not visited, not negative, and the last jump was not backward, enqueue it and mark it as visited.
  5. If the queue is exhausted without finding x, return -1 to indicate the home cannot be reached.
UML Thumbnail

Recursive Solution with Memoization

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...