1871. Jump Game VII

Time: O(n)

Space: O(n)

Intuition

From each reachable index j, you can mark a future window [j + minJump, j + maxJump]. Directly iterating every window is too slow. Instead, for each index i, ask whether there exists at least one reachable j in [i - maxJump, i - minJump]. A prefix sum over reachable flags answers this in constant time per index.

Algorithm

1Let isReachable[i] indicate whether index i can be reached; set isReachable[0] = true.
2Maintain prefixSum where prefixSum[k] = number of reachable indices in [0, k-1].
3For each i from 1 to n-1:
4 Only process if s[i] == "0".
5 Compute left = max(0, i - maxJump), right = i - minJump.
6 If left <= right and prefixSum[right + 1] - prefixSum[left] > 0, set isReachable[i] = true.
7 Update prefixSum[i + 1] = prefixSum[i] + (isReachable[i] ? 1 : 0).
8Return isReachable[n - 1].

Example Walkthrough

Input: s = "011010", minJump = 2, maxJump = 3

1.i=3 (s[3]=0): check j in [0,1]. Index 0 is reachable, so i=3 becomes reachable.
2.i=5 (s[5]=0): check j in [2,3]. Index 3 is reachable, so i=5 becomes reachable.
3.Last index becomes reachable, answer is true.

Output: true

Common Pitfalls

•Skip positions where s[i] == "1"; they cannot be landed on.
•Bounds for [i-maxJump, i-minJump] must be clamped correctly or range checks break.
•A naive nested scan over each window is O(n*maxJump) and can time out; prefix sums are essential.

1871.cs

// Approach: Dynamic programming with prefix sums over reachable indices.
// For each position i with s[i]=='0', check if any reachable index exists in [i-maxJump, i-minJump].
// Prefix sums answer this range-existence query in O(1), giving linear total time.
// Time: O(n) Space: O(n)

public class Solution
{
    public bool CanReach(string s, int minJump, int maxJump)
    {
        int n = s.Length;

        // Prefix sum array to track count of reachable positions
        // prefixSum[i] stores the count of reachable positions from index 0 to i-1
        int[] prefixSum = new int[n + 1];
        prefixSum[1] = 1; // Position 0 is reachable (starting position)

        // Dynamic programming array to track if position i is reachable
        bool[] isReachable = new bool[n];
        isReachable[0] = true; // Starting position is always reachable

        // Iterate through each position in the string
        for (int i = 1; i < n; i++)
        {
            // Can only jump to positions with '0'
            if (s[i] == '0')
            {
                // Calculate the valid range of positions we can jump from
                // We can jump from position j to i if: i - maxJump <= j <= i - minJump
                int leftBound = Math.Max(0, i - maxJump);
                int rightBound = i - minJump;

                // Check if there exists at least one reachable position in the range [leftBound, rightBound]
                // Using prefix sum to efficiently check if any position in range is reachable
                isReachable[i] = leftBound <= rightBound &&
                                 prefixSum[rightBound + 1] - prefixSum[leftBound] > 0;
            }

            // Update prefix sum array
            // Add 1 if current position is reachable, otherwise add 0
            prefixSum[i + 1] = prefixSum[i] + (isReachable[i] ? 1 : 0);
        }

        // Return whether the last position is reachable
        return isReachable[n - 1];
    }
}

Was this solution helpful?