We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Minimum Jumps to Reach Home

Number: 1757

Difficulty: Medium

Paid? No

Companies: Amazon

Problem Description

A bug is trying to reach its home located at position x on the x-axis starting from position 0. It can jump a fixed distance a forwards and fixed distance b backwards, but cannot jump backward two times in a row or onto forbidden positions. The goal is to determine the minimum number of jumps required for the bug to reach position x, or return -1 if it’s impossible.

Key Insights

  • This problem can be modeled as a state-space search where each state is determined by the current position and whether the last jump was a backward jump.
  • Use Breadth-First Search (BFS) to explore the minimum number of jumps (layers represent jump count).
  • To avoid cycles, a visited set should record states (position, last jump type) instead of just positions.
  • The search can be bounded by a reasonable maximum position since the bug is allowed to overshoot x only by a certain range.
  • Careful handling is needed when making backward jumps because two consecutive backward jumps are disallowed.

Space and Time Complexity

Time Complexity: O(N) where N is bounded by the maximum reachable state (considering the problem constraints and the BFS frontier). Space Complexity: O(N) for storing visited states in the BFS queue.

Solution

We solve the problem using BFS to ensure we get the minimum number of jumps. The state in our BFS consists of two components: the current position and a flag indicating if the last jump was backward. From each state:

  • We try a forward jump if the new position is not forbidden and within bounds.
  • We try a backward jump only if the previous jump was not backward. A set is maintained to track visited states (position, backwardFlag) to prevent cycles. The algorithm stops when the bug reaches position x. A reasonable bound is computed (for example, max(forbidden ∪ {x}) + a + b) to limit the search space.

Code Solutions

from collections import deque

def minimumJumps(forbidden, a, b, x):
    forbidden_set = set(forbidden)
    # Bound: since the bug can overshoot x, the search space can be limited.
    upper_bound = max(max(forbidden_set, default=0) + a + b, x + b)
    # Each state is (position, wasLastJumpBackward)
    queue = deque([(0, False)])
    visited = {(0, False)}
    jumps = 0

    while queue:
        for _ in range(len(queue)):
            position, backwardUsed = queue.popleft()
            # Check if reached target
            if position == x:
                return jumps

            # Try forward jump
            nextPos = position + a
            if 0 <= nextPos <= upper_bound and nextPos not in forbidden_set and (nextPos, False) not in visited:
                visited.add((nextPos, False))
                queue.append((nextPos, False))
            
            # Try backward jump only if last jump was not backward
            if not backwardUsed:
                nextPos = position - b
                if 0 <= nextPos and nextPos not in forbidden_set and (nextPos, True) not in visited:
                    visited.add((nextPos, True))
                    queue.append((nextPos, True))
        jumps += 1
    return -1

# Example usage
print(minimumJumps([14,4,18,1,15], 3, 15, 9))  # Output: 3
← Back to All Questions