Jump Game VII

NeetCode: Jump Game VII · LeetCode: 1871. Jump Game VII · Difficulty: Medium

Given a binary string s (0-indexed) and two integers minJump and maxJump, start at index 0 (guaranteed to be '0'). From index i you can jump to j if i + minJump <= j <= min(i + maxJump, n - 1) and s[j] == '0'. Return true if you can reach index n - 1.

Example

Text

Input:  s = "011010", minJump = 2, maxJump = 3      Output: true   (0 -> 3 -> 5)
Input:  s = "01101110", minJump = 2, maxJump = 3    Output: false

Brute force: look back at every possible source

Let reach[i] mean index i can be reached. Index i is reachable if s[i] == '0' and some index j in [i - maxJump, i - minJump] is reachable. Scanning that window for every i costs up to maxJump per index.

Java

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        boolean[] reach = new boolean[n];
        reach[0] = true;
        for (int i = 1; i < n; i++) {
            if (s.charAt(i) != '0' || i < minJump) {
                continue;
            }
            int lo = Math.max(0, i - maxJump);
            int hi = i - minJump;
            for (int j = lo; j <= hi; j++) {
                if (reach[j]) {
                    reach[i] = true;
                    break;
                }
            }
        }
        return reach[n - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canReach("011010", 2, 3));
        System.out.println(s.canReach("01101110", 2, 3));
        System.out.println(s.canReach("0", 1, 1));
        System.out.println(s.canReach("00", 1, 1));
        System.out.println(s.canReach("01", 1, 1));
    }
}

Output

true
false
true
true
false

Time: O(n * maxJump). Space: O(n).

Optimal: sliding window of reachable sources

Only whether the window [i - maxJump, i - minJump] contains any reachable index matters, that is, whether a count is positive. The window slides right by one each step, so the count can be maintained incrementally: moving to i, index i - minJump enters the window (add it if reachable) and index i - maxJump - 1 leaves it (subtract it if reachable). Each index enters and leaves once, so the scan is linear.

Java

class Solution {
    public boolean canReach(String s, int minJump, int maxJump) {
        int n = s.length();
        boolean[] reach = new boolean[n];
        reach[0] = true;
        int window = 0; // reachable indices in [i - maxJump, i - minJump]
        for (int i = 1; i < n; i++) {
            if (i >= minJump && reach[i - minJump]) {
                window++;
            }
            if (i > maxJump && reach[i - maxJump - 1]) {
                window--;
            }
            reach[i] = s.charAt(i) == '0' && window > 0;
        }
        return reach[n - 1];
    }
}

public class Main {
    public static void main(String[] args) {
        Solution s = new Solution();
        System.out.println(s.canReach("011010", 2, 3));
        System.out.println(s.canReach("01101110", 2, 3));
        System.out.println(s.canReach("0", 1, 1));
        System.out.println(s.canReach("00", 1, 1));
        System.out.println(s.canReach("01", 1, 1));
    }
}

Output

true
false
true
true
false

Time: O(n). Space: O(n) for the reach array.