Scale Engineer

Jump Game VII

Med
#1709Time: O(n * k), where n is the length of the string and k is `maxJump - minJump`. For each index `i`, we might scan up to `k` previous indices. In the worst case, `k` can be close to `n`, leading to an `O(n^2)` complexity.Space: O(n), where n is the length of the string `s`. This is for the `dp` array used to store the reachability of each index.
Patterns
Sliding WindowDynamic ProgrammingPrefix Sum
Data structures
String

Prompt

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

 

Constraints:

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

Approaches

3 approaches with complexity analysis and trade-offs.

This approach uses dynamic programming to solve the problem. We define an array dp where dp[i] is true if index i is reachable from index 0, and false otherwise. To determine dp[i], we check if s[i] is '0' and if there exists any previously reachable index j that can jump to i. A jump from j to i is valid if i - maxJump <= j <= i - minJump. This involves a nested loop, where the outer loop iterates through each index i and the inner loop checks the valid window of previous indices j.

Algorithm

  • Create a boolean array dp of size n, where dp[i] will be true if index i is reachable, and false otherwise.
  • Initialize dp[0] to true since we start at index 0.
  • Iterate through the string from i = 1 to n-1.
  • For each index i, if s[i] is '0', iterate through all possible previous indices j from which a jump to i is valid.
  • The valid range for a previous index j is i - maxJump <= j <= i - minJump.
  • If we find any j in this range for which dp[j] is true, it means we can reach i. We set dp[i] = true and can break the inner loop for the current i.
  • After iterating through all i, the value of dp[n-1] will tell us if the last index is reachable.

Walkthrough

In this approach, we build a boolean array dp of the same size as the input string s. dp[i] stores whether index i is reachable. We know dp[0] is true because we start there. For every other index i from 1 to n-1, we can determine its reachability based on the reachability of previous indices.

An index i is reachable if two conditions are met:

  1. The character at that index, s[i], must be '0'.
  2. There must be at least one reachable index j from which we can jump to i. The jump condition j + minJump <= i <= j + maxJump can be rearranged to find the range of j for a given i: i - maxJump <= j <= i - minJump.

So, for each i, we check if s[i] is '0'. If it is, we then scan the dp array in the range [max(0, i - maxJump), i - minJump] to see if any dp[j] is true. If we find one, we set dp[i] to true and move to the next index. The final answer is the value of dp[s.length - 1].

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

Complexity

Time

O(n * k), where n is the length of the string and k is `maxJump - minJump`. For each index `i`, we might scan up to `k` previous indices. In the worst case, `k` can be close to `n`, leading to an `O(n^2)` complexity.

Space

O(n), where n is the length of the string `s`. This is for the `dp` array used to store the reachability of each index.

Trade-offs

Pros

  • It's a direct translation of the problem's recurrence relation, making it relatively easy to understand and implement.

Cons

  • The nested loop structure leads to a high time complexity, which will result in a 'Time Limit Exceeded' error on larger inputs.

Solutions

class Solution { public boolean canReach ( String s , int minJump , int maxJump ) { int n = s . length (); int [] pre = new int [ n + 1 ]; pre [ 1 ] = 1 ; boolean [] f = new boolean [ n ]; f [ 0 ] = true ; for ( int i = 1 ; i < n ; ++ i ) { if ( s . charAt ( i ) == '0' ) { int l = Math . max ( 0 , i - maxJump ); int r = i - minJump ; f [ i ] = l <= r && pre [ r + 1 ] - pre [ l ] > 0 ; } pre [ i + 1 ] = pre [ i ] + ( f [ i ] ? 1 : 0 ); } return f [ n - 1 ]; } }

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem