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

Jump Game VII

Difficulty: Medium

Problem Description

You are given a 0-indexed binary string s and two integers minJump and maxJump. In the beginning, you are standing at index 0, which is equal to '0'. You can move from index i to index j if the following conditions are fulfilled:

  • i + minJump <= j <= min(i + maxJump, s.length - 1), and
  • s[j] == '0'.

Return true if you can reach index s.length - 1 in s, or false otherwise.

Key Insights

  • You can only jump to indices that are '0'.
  • The range of jumps is defined by minJump and maxJump.
  • A breadth-first search (BFS) or sliding window approach can be used to explore reachable indices efficiently.
  • Keeping track of the farthest reachable index helps optimize the search process.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(1)

Solution

The problem can be approached using a breadth-first search (BFS) strategy. We maintain a variable to track the farthest index that can be reached. As we iterate through the string, we look for valid jump positions that satisfy the conditions. We use a single loop to traverse the string, checking if we can reach the end based on the allowed jumping range. This ensures that we do not revisit indices unnecessarily, optimizing our search.

Code Solutions

def canReach(s: str, minJump: int, maxJump: int) -> bool:
    n = len(s)
    farthest = 0  # The farthest index we can reach
    for i in range(n):
        if i > farthest:  # If we reach an index that is not reachable
            return False
        if s[i] == '0' and i >= minJump:
            farthest = max(farthest, i + maxJump)  # Update farthest index
    return farthest >= n - 1  # Check if we can reach the last index
← Back to All Questions