Jump Game VII

How it works

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.

Steps

1. Create a DP array with dp[0] = true. Initialize pointer j = 0.
2. 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.
3. Return dp[n - 1].

Complexity

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

Things to watch for

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.

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]

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        if (s[n - 1] == '1') {
            return false;
        }

        vector<bool> dp(n, false);
        dp[0] = true;
        int j = 0;

        for (int i = 0; i < n; i++) {
            if (!dp[i]) {
                continue;
            }
            j = max(j, i + minJump);
            while (j < min(i + maxJump + 1, n)) {
                if (s[j] == '0') {
                    dp[j] = true;
                }
                j++;
            }
        }

        return dp[n - 1];
    }
};