1871. Jump Game VII

1871. Jump Game VII

Difficulty: Medium

Topics: Staff, String, Dynamic Programming, Sliding Window, Prefix Sum, Weekly Contest 242

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 = "011010", minJump = 2, maxJump = 3
• Output: true
• Explanation:
  • In the first step, move from index 0 to index 3.
  • In the second step, move from index 3 to index 5.

Example 2:

• Input: s = "01101110", minJump = 2, maxJump = 3
• Output: false

Example 3:

• Input: s = "0", minJump = 1, maxJump = 1
• Output: true

Constraints:

• 2 <= s.length <= 10⁵
• s[i] is either '0' or '1'.
• s[0] == '0'
• 1 <= minJump <= maxJump < s.length

Hint:

1. Consider for each reachable index i the interval [i + a, i + b].
2. Use partial sums to mark the intervals as reachable.

Solution:

This solution determines whether it’s possible to jump from index 0 to the last index of a binary string s using jumps of length between minJump and maxJump, landing only on '0'.

It uses dynamic programming with a prefix sum array to efficiently track reachable indices without recalculating ranges repeatedly.

Approach:

• Dynamic programming array dp where dp[i] indicates whether index i is reachable.
• Prefix sum array prefix where prefix[i] stores the number of reachable indices up to i.
• For each index i, check if there’s any reachable index in the range [i - maxJump, i - minJump].
• Use the prefix sum to get the count of reachable indices in that range in O(1).
• If count > 0 and s[i] == '0', mark dp[i] as reachable.
• Update prefix sum accordingly.

Let's implement this solution in PHP: 1871. Jump Game VII

<?php
/**
 * @param String $s
 * @param Integer $minJump
 * @param Integer $maxJump
 * @return Boolean
 */
function canReach(string $s, int $minJump, int $maxJump): bool
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo canReach("011010", 2, 3) . "\n";           // Output: true
echo canReach("01101110", 2, 3) . "\n";         // Output: false
echo canReach("0", 1, 1) . "\n";                // Output: true
?>

Explanation:

• Initialize dp[0] = true and prefix[0] = 1.
• Loop from i = 1 to n-1:
  • Compute left = i - maxJump and right = i - minJump.
  • If right < 0, no jumps can land here → skip.
  • Adjust left to be at least 0.
  • Compute reachable count in [left, right] using prefix sums.
  • If reachable count > 0 and s[i] == '0', mark dp[i] = true.
  • Update prefix[i] = prefix[i-1] + (dp[i] ? 1 : 0).
• Return dp[n-1].

Complexity

• Time Complexity: O(n), Each index is processed once with O(1) range sum queries.
• Space Complexity: O(n), For dp and prefix arrays of length n.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub

Comments

[PracHub]

Using a prefix sum array to optimize range-checking in Jump Game VII is a clever way to bring the time complexity down to O(n). It efficiently handles repeated conditions without using too much space. This approach is similar to dynamic programming strategies we often see in algorithmic questions, especially those with optimized range queries. Developers wanting to practice this pattern can find a range of recent tech interview questions on prachub.com that deal with similar challenges.