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

Jump Game VII

Number: 2001

Difficulty: Medium

Paid? No

Companies: Google

Problem Description

Given a binary string s and two integers minJump and maxJump, you start at index 0 (which is guaranteed to be '0'). From any index i, you can jump to any index j satisfying i + minJump ≤ j ≤ min(i + maxJump, s.length - 1) provided that s[j] is '0'. The goal is to determine whether you can reach the last index of the string.

Key Insights

  • A straightforward BFS or DFS would be too slow for large inputs due to overlapping subproblems.
  • Use dynamic programming with a sliding window (prefix sum) to efficiently track the cumulative reachability.
  • Instead of checking each jump individually, maintain a sliding window sum over the dp values that denote whether previous positions are reachable.
  • When the sliding window moves, add the new dp value entering the window and subtract the dp value leaving the window.
  • The cell is marked reachable only if it is '0' and there exists at least one previous reachable index within the jump range.

Space and Time Complexity

Time Complexity: O(n) where n is the length of the string. Space Complexity: O(n) for the dp array.

Solution

The solution uses a dynamic programming approach combined with a sliding window technique. We create a boolean array dp where dp[i] indicates whether index i is reachable. We initialize dp[0] as true because we start from index 0. A variable (reachable) is used to maintain the count of reachable indices in the current window. For each index i, if i is within minJump distance from a previous index, we add dp[i - minJump] to reachable. If the index is beyond maxJump, we subtract dp[i - maxJump - 1] from reachable as its contribution is no longer valid. If the current character s[i] is '0' and reachable is greater than zero, we mark dp[i] as true. Finally, dp[s.length - 1] gives the answer.

Code Solutions

def canReach(s: str, minJump: int, maxJump: int) -> bool:
    n = len(s)
    # dp[i] is True if index i is reachable, False otherwise
    dp = [False] * n
    dp[0] = True
    
    # variable to keep track of the cumulative count of reachable indices in the window
    reachable = 0
    for i in range(1, n):
        # If i is at least minJump steps ahead, add the dp value that enters the window.
        if i >= minJump:
            reachable += dp[i - minJump]
        # If i is beyond maxJump, subtract the dp value that leaves the window.
        if i > maxJump:
            reachable -= dp[i - maxJump - 1]
        # Mark index i as reachable if s[i] is '0' and there is at least one reachable index in the window.
        if s[i] == '0' and reachable > 0:
            dp[i] = True
    return dp[-1]

# Example usage:
print(canReach("011010", 2, 3))  # Expected output: True
← Back to All Questions