Jump Game VII - Practice Coding Problems

Jump Game VII - Problem

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.

Input & Output

Example 1 — Basic Jump Sequence

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

› Output: true

💡 Note: Start at index 0, jump to index 3 (jump of size 3), then jump to index 5 (jump of size 2). Both positions contain '0' and are within jump constraints.

Example 2 — Blocked Path

$ Input: s = "01101110", minJump = 2, maxJump = 3

› Output: false

💡 Note: From index 0, we can reach index 2 or 3. From index 3, we can reach indices 5 or 6, but both contain '1'. No valid path to the last index.

Example 3 — Minimum Jump Only

$ Input: s = "0101", minJump = 1, maxJump = 1

› Output: false

💡 Note: From index 0, jump to index 1 ('1' - invalid). Cannot proceed further, so cannot reach index 3.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Binary string with jump constraints

Process

Find valid jumps avoiding '1' positions

Output

True if last position is reachable

Key Takeaway

🎯 Key Insight: Use sliding window with DP to efficiently track which positions can jump to current position

Asked in

f Meta 25 G Google 20 a Amazon 18 M Microsoft 15

The key insight is to use dynamic programming to track reachable positions, optimized with a sliding window technique. The sliding window approach achieves optimal O(n) time by maintaining a count of reachable positions in the current jump range. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Memoization (Top-Down DP)	O(n × (maxJump - minJump))	O(n)	Cache DFS results to avoid redundant computations
Brute Force DFS	O(2^n)	O(n)	Try all possible paths using depth-first search
Dynamic Programming (Bottom-Up)	O(n × (maxJump - minJump))	O(n)	Build reachability table from left to right
Sliding Window + Prefix Sum	O(n)	O(n)	Use sliding window to efficiently track reachable positions

Memoization (Top-Down DP) — Algorithm Steps

Use DFS with memoization
Cache results for each position
Return cached result if already computed
Otherwise compute and cache before returning

Visualization

Tap to expand

Step-by-Step Walkthrough

First Visit

Compute and cache result

Subsequent Visits

Return cached result immediately

Efficiency

Each position computed only once

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

int min(int a, int b) {
    return a < b ? a : b;
}

bool dfs(const char* s, int pos, int minJump, int maxJump, int n, int* memo) {
    if (pos == n - 1) {
        return true;
    }
    if (memo[pos] != -1) {
        return memo[pos];
    }
    
    for (int nextPos = pos + minJump; nextPos <= min(pos + maxJump, n - 1); nextPos++) {
        if (s[nextPos] == '0' && dfs(s, nextPos, minJump, maxJump, n, memo)) {
            memo[pos] = 1;
            return true;
        }
    }
    
    memo[pos] = 0;
    return false;
}

bool solution(const char* s, int minJump, int maxJump) {
    int n = strlen(s);
    int* memo = malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        memo[i] = -1;
    }
    
    bool result = dfs(s, 0, minJump, maxJump, n, memo);
    free(memo);
    return result;
}

int main() {
    char s[100001];
    int minJump, maxJump;
    
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    
    scanf("%d", &minJump);
    scanf("%d", &maxJump);
    
    bool result = solution(s, minJump, maxJump);
    printf(result ? "true\n" : "false\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × (maxJump - minJump))

Each position computed once, with up to (maxJump-minJump) transitions

✓ Linear Growth

Space Complexity

O(n)

Memoization array and recursion stack both use O(n) space

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Memoization (Top-Down DP) — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler