Leetcode 1871: Jump Game VII

Input: You are provided with a binary string `s` and two integers `minJump` and `maxJump`. The string `s` contains only '0' and '1'.

Example: For s = "011010", minJump = 2, maxJump = 3.

Constraints:

• 2 <= s.length <= 105

• s[i] is either '0' or '1'.

• s[0] == '0'

• 1 <= minJump <= maxJump < s.length

Output: Return `true` if it’s possible to reach the last index, or `false` if it’s impossible.

Example: For the input s = "011010", minJump = 2, maxJump = 3, the output is `true`.

Constraints:

• The output must be a boolean value.

Goal: We need to determine if there exists a valid sequence of jumps that reaches the last index.

Steps:

• Initialize a dynamic programming array `dp` to track which indices can be reached.

• Iterate through the string and use the previous `dp` values to determine if the current index can be reached.

• Use sliding window technique to efficiently update the reachable indices based on `minJump` and `maxJump`.

Goal: The length of the string `s` and the values for `minJump` and `maxJump` must satisfy the given constraints.

Steps:

• 2 <= s.length <= 105

• 1 <= minJump <= maxJump < s.length

• s[0] == '0'

• s[i] is either '0' or '1'

Assumptions:

• The string always starts with '0' at index 0.

• At least one valid path exists in some test cases.

• Input: For the input s = "011010", minJump = 2, maxJump = 3.

• Explanation: The first move can be from index 0 to index 3 (using minJump = 2). From there, you can move from index 3 to index 5, reaching the last index.

• Input: For the input s = "01101110", minJump = 2, maxJump = 3.

• Explanation: No valid jumps exist because there’s no way to reach the last index.

Approach: We use a dynamic programming approach where we maintain a sliding window to efficiently track the reachable indices based on `minJump` and `maxJump`.

Observations:

• We need to efficiently calculate which indices are reachable from each position.

• Using a sliding window of reachable indices helps avoid unnecessary recalculations.

• The goal is to minimize the time complexity while ensuring correctness by checking each possible jump within the given constraints.

Steps:

• Initialize a DP array to track reachable indices.

• Use a sliding window technique to update which indices are reachable.

• Check if the last index can be reached by iterating through the DP array.

Empty Inputs:

• Not applicable as the string length is at least 2.

Large Inputs:

• Ensure that the algorithm scales for larger values of `s.length`.

Special Values:

• Test with a string of length 2, where only the first and last index can be reached.

Constraints:

• Check edge cases for large values of `minJump` and `maxJump`.

bool canReach(string s, int mnj, int mxj) {
    int n = s.length();
    vector<bool> dp(n, false);
    dp[0] = true;
    int pre = 0;
    for(int i = 0; i < n; i++) {
    
        if(i >= mnj && dp[i - mnj])
            pre++;

        if(i > mxj && dp[i - mxj -1])
            pre--;

        if (pre > 0) dp[i] = s[i] == '0';       
    }
    return dp[n - 1];
}

1 : Initialization

bool canReach(string s, int mnj, int mxj) {

Define the function to determine reachability in a binary string with jump constraints.

2 : Initialization

    int n = s.length();

Calculate the length of the binary string.

3 : Initialization

    vector<bool> dp(n, false);

Initialize a DP array to track reachable indices, all set to false initially.

4 : Initialization

    dp[0] = true;

Mark the starting index as reachable.

5 : Sliding Window

    int pre = 0;

Initialize a variable to track the sliding window sum for reachability.

6 : Loop

    for(int i = 0; i < n; i++) {

Iterate through each index of the binary string.

7 : Sliding Window

        if(i >= mnj && dp[i - mnj])

If within range, increment the sliding window sum if the jump from a reachable index is valid.

8 : Sliding Window

            pre++;

Increase the sliding window sum for valid jumps.

9 : Sliding Window

        if(i > mxj && dp[i - mxj -1])

If the jump exceeds the maximum constraint, decrement the sliding window sum.

10 : Sliding Window

            pre--;

Decrease the sliding window sum for invalid jumps.

11 : Condition

        if (pre > 0) dp[i] = s[i] == '0';

Mark the current index as reachable if the sliding window sum is positive and the index is valid ('0').

12 : Return

    return dp[n - 1];

Return whether the last index is reachable based on the DP array.

Best Case: O(n)

Average Case: O(n)

Worst Case: O(n)

Description: The solution iterates over the string once while updating reachable indices, resulting in a time complexity of O(n).

Best Case: O(n)

Worst Case: O(n)

Description: We use a DP array of size n to store the reachable states, hence the space complexity is O(n).

Leetcode 1871: Jump Game VII

Explore →