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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Jumps to Reach Home

Difficulty: Medium

Problem Description

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 specific rules: it can jump exactly a positions forward, b positions backward, cannot jump backward twice in a row, and cannot jump to forbidden positions. The bug may jump forward beyond its home but cannot jump to negative integers. Given an array of forbidden positions, integers a, b, and x, return the minimum number of jumps needed for the bug to reach its home. If impossible, return -1.

Key Insights

  • The bug can jump forward and backward, but cannot jump backward consecutively.
  • The problem can be modeled as a graph traversal problem where each position is a node, and valid jumps are edges.
  • Breadth-First Search (BFS) is suitable for finding the shortest path in an unweighted graph, which applies here.
  • The forbidden positions must be represented as a set for O(1) look-up time.
  • The search space is limited to positions greater than or equal to 0 and less than the maximum of the forbidden positions plus a reasonable margin.

Space and Time Complexity

Time Complexity: O(max(x, max(forbidden)) + a + b), where we consider the maximum position we may need to explore. Space Complexity: O(max(x, max(forbidden))) for the queue and visited set.

Solution

We can use a breadth-first search (BFS) approach to explore all possible positions the bug can jump to.

  1. Start at position 0 and initialize a queue to manage the current position and the number of jumps taken.
  2. Maintain a visited set to avoid revisiting positions and a set for forbidden positions.
  3. For each position, attempt to jump forward by 'a' and backward by 'b', ensuring we do not jump to forbidden positions and do not jump backward twice in a row.
  4. If we reach the target position 'x', return the number of jumps.
  5. If the queue is exhausted without reaching 'x', return -1.

Code Solutions

from collections import deque

def minimumJumps(forbidden, a, b, x):
    forbidden_set = set(forbidden)
    queue = deque([(0, 0, False)])  # (current_position, jumps, last_was_backward)
    visited = set([0])

    while queue:
        position, jumps, last_backward = queue.popleft()

        # Check if we reached the target
        if position == x:
            return jumps

        # Jump forward
        next_forward = position + a
        if next_forward not in forbidden_set and next_forward >= 0 and next_forward <= 2000 + a + b:
            if next_forward not in visited:
                visited.add(next_forward)
                queue.append((next_forward, jumps + 1, False))

        # Jump backward (only if the last jump wasn't backward)
        if not last_backward:
            next_backward = position - b
            if next_backward >= 0 and next_backward not in forbidden_set:
                if next_backward not in visited:
                    visited.add(next_backward)
                    queue.append((next_backward, jumps + 1, True))

    return -1
← Back to All Questions