1871. Jump Game VII - Explanation

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.

Example 1:

Input: s = "00110010", minJump = 2, maxJump = 4

Output: true

Explanation: The order of jumps is: indices 0 -> 4 -> 7.

Example 2:

Input: s = "0010", minJump = 1, maxJump = 1

Output: false

Constraints:

2 <= s.length <= 100,000
s[i] is either '0' or '1'.
s[0] == '0'
1 <= minJump <= maxJump < s.length

Company Tags

Please upgrade to NeetCode Pro to view company tags.

1. Brute Force (Memoization)

Intuition

From each position, we can jump to any position within the range [i + minJump, i + maxJump] if that position contains '0'. We use recursion with memoization to explore all valid jumps. Starting from index 0, we try every reachable position and recursively check if we can reach the end. Memoization prevents recalculating the same positions.

Algorithm

Create a memoization array initialized to null/unknown.
Define a recursive function dfs(i):
- If already computed, return the cached result.
- Mark the current position as unreachable initially.
- Try all positions j in range [i + minJump, i + maxJump].
- If s[j] == '0' and dfs(j) returns true, mark current as reachable.
Return the result for index 0.

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        dp = [None] * n
        dp[n - 1] = True

        def dfs(i):
            if dp[i] is not None:
                return dp[i]

            dp[i] = False
            for j in range(i + minJump, min(n, i + maxJump + 1)):
                if s[j] == '0' and dfs(j):
                    dp[i] = True
                    break

            return dp[i]

        if s[-1] == '1':
            return False
        return dfs(0)

Time & Space Complexity

Time complexity: $O(n * m)$
Space complexity: $O(n)$

Where $n$ is the length of the string $s$ and $m$ is the given range of the jump $(maxJump - minJump + 1)$ .

2. Breadth First Search

Intuition

BFS naturally explores positions level by level, where each level represents positions reachable in one jump. The key optimization is tracking the farthest index we've already processed. When processing position i, we only need to check new positions starting from max(i + minJump, farthest + 1) to avoid revisiting positions already added to the queue.

Algorithm

Initialize a queue with position 0 and track farthest = 0.
While the queue is not empty:
- Dequeue position i.
- Compute start = max(i + minJump, farthest + 1).
- For each j from start to min(i + maxJump, n - 1):
  - If s[j] == '0', enqueue j. If j is the last index, return true.
- Update farthest = i + maxJump.
Return false if the queue empties without reaching the end.

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        q = deque([0])
        farthest = 0

        while q:
            i = q.popleft()
            start = max(i + minJump, farthest + 1)
            for j in range(start, min(i + maxJump + 1, len(s))):
                if s[j] == "0":
                    q.append(j)
                    if j == len(s) - 1:
                        return True
            farthest = i + maxJump

        return False

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

3. Dynamic Programming (Sliding Window)

Intuition

Position i is reachable if any position in [i - maxJump, i - minJump] is reachable (and s[i] == '0'). Instead of checking all positions in this range for each i, we maintain a running count of reachable positions within the window. As we move forward, we add newly entering positions to the count and remove positions that exit the window.

Algorithm

Create a DP array where dp[i] indicates if position i is reachable.
Set dp[0] = true and initialize count cnt = 0.
For each position i from 1 to n - 1:
- If i >= minJump and dp[i - minJump] is true, increment cnt.
- If i > maxJump and dp[i - maxJump - 1] is true, decrement cnt.
- If cnt > 0 and s[i] == '0', set dp[i] = true.
Return dp[n - 1].

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        if s[n - 1] == '1':
            return False

        dp = [False] * n
        dp[0] = True
        cnt = 0
        for i in range(1, n):
            if i >= minJump and dp[i - minJump]:
                cnt += 1
            if i > maxJump and dp[i - maxJump - 1]:
                cnt -= 1
            if cnt > 0 and s[i] == '0':
                dp[i] = True

        return dp[n - 1]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

4. Dynamic Programming (Two Pointers)

Intuition

Instead of tracking a count, we use a pointer j to remember the farthest position we've marked as reachable so far. From each reachable position i, we can mark all positions in [i + minJump, i + maxJump] as reachable. The pointer j ensures we never mark the same position twice, achieving linear time.

Algorithm

Create a DP array with dp[0] = true. Initialize pointer j = 0.
For each position i from 0 to n - 1:
- If dp[i] is false, skip to the next iteration.
- Update j = max(j, i + minJump) to start from where we left off.
- Mark all positions from j to min(i + maxJump, n - 1) where s[j] == '0' as reachable.
- Increment j after processing each position.
Return dp[n - 1].

class Solution:
    def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
        n = len(s)
        if s[n - 1] == '1':
            return False

        dp = [False] * n
        dp[0] = True
        j = 0
        for i in range(n):
            if dp[i] == False:
                continue

            j = max(j, i + minJump)
            while j < min(i + maxJump + 1, n):
                if s[j] == '0':
                    dp[j] = True
                j += 1

        return dp[n - 1]

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(n)$

Common Pitfalls

Forgetting to Check the Last Character

Before starting any traversal, verify that s[n-1] == '0'. If the destination is blocked, immediately return false. Skipping this check wastes computation on an impossible path.

Off-by-One Errors in Jump Range

The valid jump range from position i is [i + minJump, i + maxJump] inclusive. Common mistakes include using i + maxJump - 1 or forgetting to clamp the upper bound to n - 1. Always verify your loop bounds match the problem constraints.

Revisiting Already Processed Positions

In BFS or DP approaches, failing to track which positions have been visited or marked leads to exponential blowup. Use a farthest pointer or visited array to ensure each index is processed at most once.