Problem Description

You are given a binary string s (containing only '0's and '1's) where you start at index 0. The character at index 0 is always '0'. Your goal is to reach the last index of the string by jumping.

The jumping rules are:

• From any position i, you can jump to position j if:
  • The jump distance is within the allowed range: i + minJump <= j <= min(i + maxJump, s.length - 1)
  • The destination position has a '0': s[j] == '0'

You need to determine if it's possible to reach the last index of the string following these rules.

For example, if you have s = "011010", minJump = 2, and maxJump = 3:

• From index 0, you can jump to indices 2 or 3 (within range [0+2, 0+3])
• Index 2 has '1', so you can't land there
• Index 3 has '0', so you can jump there
• From index 3, you can jump to index 5 (within range [3+2, 3+3])
• Index 5 has '0', so you can reach it
• Therefore, the answer would be true

The function should return true if you can reach the last index, and false otherwise.

Intuition

The key insight is that this is a reachability problem where we need to determine if each position can be reached from previously reachable positions. We can think of it as building a path from index 0 to the last index, where each step must satisfy the jumping constraints.

The natural approach is dynamic programming - for each position i, we check if it can be reached from any valid previous position. A position i is reachable if:

1. The character at position i is '0' (we can only land on '0's)
2. There exists at least one reachable position j from which we can jump to i

For the second condition, position j must satisfy: i - maxJump <= j <= i - minJump. This means we need to check if there's any reachable position within this range.

Here's where the optimization comes in: instead of checking each position in the range individually (which would be O(maxJump - minJump) for each position), we can use a prefix sum array to answer "is there any reachable position in range [l, r]?" in O(1) time.

The prefix sum array pre[i] stores the count of reachable positions in the first i positions. If pre[r+1] - pre[l] > 0, it means there's at least one reachable position in the range [l, r]. This transforms our problem from O(n * (maxJump - minJump)) to O(n) time complexity.

We build the solution incrementally: starting from index 0 (which is always reachable), we determine the reachability of each subsequent position based on whether we can jump to it from any previously reached position. The prefix sum array helps us efficiently check if any valid jumping position exists within the required range.

Learn more about Dynamic Programming, Prefix Sum and Sliding Window patterns.

Solution Approach

We implement the solution using prefix sum combined with dynamic programming:

Data Structures:

• pre: A prefix sum array of length n+1 where pre[i] represents the count of reachable positions in the first i positions
• f: A boolean array of length n where f[i] indicates whether position i is reachable

Initialization:

• pre[1] = 1: Since we start at index 0, the first position is reachable
• f[0] = True: Position 0 is our starting point
• All other positions in f are initially False

Algorithm Steps:

1. Iterate through each position i from 1 to n-1:

2. Check if s[i] == '0' (we can only land on '0's):

   • If it's '0', determine if we can reach position i from any valid previous position
   • Calculate the valid jumping range: positions from which we can jump to i
     • Left boundary: l = max(0, i - maxJump) (can't go below index 0)
     • Right boundary: r = i - minJump

3. Check reachability using prefix sum:

   • If l <= r (valid range exists) and pre[r+1] - pre[l] > 0 (at least one reachable position exists in range)
   • Then f[i] = True, otherwise f[i] = False

4. Update the prefix sum array:

   • pre[i+1] = pre[i] + f[i]
   • This adds 1 to the count if position i is reachable, otherwise adds 0

5. Return f[-1] (the reachability of the last position)

Time Complexity: O(n) - We iterate through the string once, and each position requires O(1) operations thanks to the prefix sum optimization.

Space Complexity: O(n) - We use two arrays of size approximately n.

The elegance of this solution lies in using the prefix sum to convert range queries ("is there any reachable position in range [l, r]?") from O(range_size) to O(1), making the overall algorithm linear time.

Example Walkthrough

Let's walk through the solution with s = "0110100", minJump = 2, and maxJump = 3.

Initial Setup:

• n = 7 (length of string)
• f = [True, False, False, False, False, False, False] (only position 0 is initially reachable)
• pre = [0, 1, 0, 0, 0, 0, 0, 0] (prefix sum array, pre[1] = 1 since position 0 is reachable)

Step-by-step iteration:

i = 1: s[1] = '1'

• Cannot land on '1', so f[1] = False
• Update: pre[2] = pre[1] + 0 = 1

i = 2: s[2] = '1'

• Cannot land on '1', so f[2] = False
• Update: pre[3] = pre[2] + 0 = 1

i = 3: s[3] = '0'

• Can potentially land here since it's '0'
• Calculate jump range: who can jump to position 3?
  • l = max(0, 3 - 3) = 0 (furthest position that can reach here)
  • r = 3 - 2 = 1 (closest position that can reach here)
• Check if any position in range [0, 1] is reachable:
  • pre[2] - pre[0] = 1 - 0 = 1 > 0 ✓
  • Position 0 is reachable and can jump to position 3!
• Set f[3] = True
• Update: pre[4] = pre[3] + 1 = 2

i = 4: s[4] = '1'

• Cannot land on '1', so f[4] = False
• Update: pre[5] = pre[4] + 0 = 2

i = 5: s[5] = '0'

• Can potentially land here since it's '0'
• Calculate jump range:
  • l = max(0, 5 - 3) = 2
  • r = 5 - 2 = 3
• Check if any position in range [2, 3] is reachable:
  • pre[4] - pre[2] = 2 - 1 = 1 > 0 ✓
  • Position 3 is reachable and can jump to position 5!
• Set f[5] = True
• Update: pre[6] = pre[5] + 1 = 3

i = 6: s[6] = '0'

• Can potentially land here since it's '0'
• Calculate jump range:
  • l = max(0, 6 - 3) = 3
  • r = 6 - 2 = 4
• Check if any position in range [3, 4] is reachable:
  • pre[5] - pre[3] = 2 - 1 = 1 > 0 ✓
  • Position 3 is reachable and can jump to position 6!
• Set f[6] = True
• Update: pre[7] = pre[6] + 1 = 4

Final Result:

• f[6] = True, so we can reach the last index
• The path taken: 0 → 3 → 6

The prefix sum optimization allows us to check "is any position in range [l, r] reachable?" in O(1) time by computing pre[r+1] - pre[l]. If this value is greater than 0, at least one position in that range is reachable.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm iterates through the string once with a single for loop from index 1 to n-1. Within each iteration:

• Calculating max(0, i - maxJump) and i - minJump takes O(1) time
• Checking if s[i] == "0" takes O(1) time
• Computing pre[r + 1] - pre[l] takes O(1) time since we're accessing precomputed prefix sum values
• Updating pre[i + 1] takes O(1) time

Since we perform O(1) operations for each of the n positions, the total time complexity is O(n).

Space Complexity: O(n)

The algorithm uses:

• Array pre of size n + 1 to store prefix sums: O(n) space
• Array f of size n to store reachability status: O(n) space
• A few integer variables (n, i, l, r): O(1) space

The total space complexity is O(n) + O(n) + O(1) = O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Range Calculation for Jump Sources

Pitfall: A common mistake is incorrectly calculating which positions can jump TO position i, leading to checking the wrong range of source positions.

Incorrect approach:

# Wrong: This calculates where we can jump TO from position i
left_bound = i + minJump
right_bound = min(i + maxJump, n - 1)

Correct approach:

# Correct: Calculate which positions can jump FROM to reach position i
left_bound = max(0, i - maxJump)  # Can't go below index 0
right_bound = i - minJump          # Must jump at least minJump distance

The key insight is that when processing position i, we need to look BACKWARD to find positions that can reach i, not forward.

2. Off-by-One Errors in Prefix Sum Indexing

Pitfall: Misaligning the prefix sum array indices with the actual position indices, causing incorrect range sum calculations.

Incorrect approach:

# Wrong: Inconsistent indexing
count_reachable = prefix_sum[right_bound] - prefix_sum[left_bound - 1]
# This fails when left_bound = 0 (index out of bounds)

Correct approach:

# Correct: Consistent 1-indexed prefix sum
prefix_sum = [0] * (n + 1)  # Size n+1 for 1-indexed prefix sum
count_reachable = prefix_sum[right_bound + 1] - prefix_sum[left_bound]

3. Forgetting to Check Valid Range Bounds

Pitfall: Not verifying that the calculated range [left_bound, right_bound] is valid before using it.

Incorrect approach:

# Wrong: Doesn't check if range is valid
count_reachable = prefix_sum[right_bound + 1] - prefix_sum[left_bound]
reachable[i] = count_reachable > 0

Correct approach:

# Correct: Check range validity first
if left_bound <= right_bound:
    count_reachable = prefix_sum[right_bound + 1] - prefix_sum[left_bound]
    reachable[i] = count_reachable > 0
# If left_bound > right_bound, no valid source positions exist

This is crucial when i < minJump, where right_bound = i - minJump becomes negative, making the range invalid.

4. Not Handling Edge Cases Properly

Pitfall: Failing to handle special cases like when the target is already at position 0 or when minJump is larger than the string length.

Solution: Always verify:

• The starting position (index 0) has '0' (given in problem)
• The last position has '0' (otherwise it's unreachable regardless)
• Early return if n - 1 < minJump (impossible to reach the end)

# Add early termination checks
if s[-1] == '1':
    return False  # Can't land on '1'
if len(s) == 1:
    return True   # Already at the end
if minJump >= len(s):
    return False  # Can't reach the end with minimum jump