Jump Game VII
MedPrompt
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), ands[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 <= 105s[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
dpof sizen, wheredp[i]will betrueif indexiis reachable, andfalseotherwise. - Initialize
dp[0]totruesince we start at index 0. - Iterate through the string from
i = 1ton-1. - For each index
i, ifs[i]is'0', iterate through all possible previous indicesjfrom which a jump toiis valid. - The valid range for a previous index
jisi - maxJump <= j <= i - minJump. - If we find any
jin this range for whichdp[j]istrue, it means we can reachi. We setdp[i] = trueand can break the inner loop for the currenti. - After iterating through all
i, the value ofdp[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:
- The character at that index,
s[i], must be'0'. - There must be at least one reachable index
jfrom which we can jump toi. The jump conditionj + minJump <= i <= j + maxJumpcan be rearranged to find the range ofjfor a giveni: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.
This approach optimizes the naive DP solution by avoiding the inner loop. The key observation is that as we move from index i to i+1, the window of previous indices [i - maxJump, i - minJump] slides. Instead of re-scanning this window every time, we can maintain a count of reachable positions within it. We use a single variable, reachableCount, to track this. When the window slides, we update the count in O(1) time by adding the contribution of the index that enters the window and subtracting the contribution of the index that leaves.
Algorithm
- Create a boolean array
dpof sizen, withdp[0] = true. - Initialize a counter
reachableCount = 0. - Iterate
ifrom1ton-1. - At each
i, updatereachableCountbased on the window[i - maxJump, i - minJump]. This window slides asiincreases.- If
i >= minJumpanddp[i - minJump]was reachable, it means a new potential jump position has entered our consideration window. IncrementreachableCount. - If
i > maxJumpanddp[i - maxJump - 1]was reachable, it means a position has just slid out of our consideration window. DecrementreachableCount.
- If
- If
s[i] == '0'andreachableCount > 0, it means there's at least one valid position to jump from, so we setdp[i] = true. - Return
dp[n-1]after the loop.
Walkthrough
The bottleneck in the previous DP approach is the repeated scanning of the window [i - maxJump, i - minJump]. We can optimize this by realizing that this is a sliding window problem. We can maintain a count of how many reachable positions (dp[j] == true) are in the current window.
Let's maintain a variable reachableCount. As we iterate i from 1 to n-1, reachableCount will store the number of reachable indices in the range [i - maxJump, i - minJump]. We can update this count in constant time. When we move from i-1 to i, the index i - minJump enters the window's right side, and i - maxJump - 1 leaves the window's left side.
So, at each step i, we first update reachableCount based on dp[i - minJump] (entering) and dp[i - maxJump - 1] (leaving). Then, if s[i] == '0' and reachableCount > 0, we know i is reachable and set dp[i] = true. This process eliminates the inner loop, reducing the time complexity to linear.
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; int reachableCount = 0; for (int i = 1; i < n; i++) { if (i >= minJump) { if (dp[i - minJump]) { reachableCount++; } } if (i > maxJump) { if (dp[i - maxJump - 1]) { reachableCount--; } } if (s.charAt(i) == '0' && reachableCount > 0) { dp[i] = true; } } return dp[n - 1]; }}Complexity
Time
O(n). We iterate through the string once, and all operations inside the loop (updating count, checking conditions) are constant time.
Space
O(n), for the `dp` array. Although we optimize the time, we still need to store the reachability of all previous indices.
Trade-offs
Pros
Achieves linear time complexity, which is efficient enough to pass for the given constraints.
The logic is a direct optimization of the DP approach and is relatively intuitive.
Cons
While the time complexity is optimal, this approach still requires O(n) extra space for the DP array.
This approach provides the most optimal solution in terms of space complexity. Instead of using a full dp array to remember every reachable state, we only need to keep track of the reachable indices within the current sliding window. A deque is a perfect data structure for this. It will store the indices of reachable '0's. As we iterate through the string, we use the deque to find out in O(1) time if there's a valid position to jump from. We add newly found reachable indices to the back of the deque and remove indices that are too far from the front.
Algorithm
- If
s[n-1]is'1', returnfalseimmediately. - Initialize a deque (double-ended queue) and add the starting index
0. - Iterate
ifrom1ton-1. - For each
i, first prune the deque from the front. Remove any indexjsuch thatj < i - maxJump, as they are now too far to jump from. - After pruning, check the index at the front of the deque,
j = deque.front(). Ifj <= i - minJump, it means there is a reachable position within the valid jump range[i - maxJump, i - minJump]. - If
s[i]is'0'and the condition above is met, then indexiis reachable. Addito the back of the deque. - After the loop, the last index
n-1is reachable if and only if it was added to the deque. This can be checked by seeing if the last element in the deque isn-1.
Walkthrough
To optimize space, we can observe that we don't need to store the reachability of all past indices, only those that could potentially be used for future jumps. These are the reachable indices that fall within a sliding window.
A deque can efficiently manage this set of relevant reachable indices. We will store the indices j where s[j] == '0' and j is reachable.
As we iterate with i from 1 to n-1:
- Slide the window: We remove indices from the front of the deque that are no longer reachable because they are too far behind. Specifically, any index
jin the deque wherej < i - maxJumpis removed. - Check for reachability: After sliding, we look at the front of the deque. If the deque is not empty and its front element
jsatisfiesj <= i - minJump, it means there is a valid reachable position from which we can jump toi. - Update: If
s[i]is'0'and the reachability check passes, we addito the back of the deque, as it is now a new reachable position.
Finally, we check if n-1 was ever added to the deque. The last element in the deque will be the furthest reachable index we found. If it's n-1, we've succeeded.
import java.util.Deque;import java.util.LinkedList; class Solution { public boolean canReach(String s, int minJump, int maxJump) { int n = s.length(); if (s.charAt(n - 1) == '1') { return false; } Deque<Integer> queue = new LinkedList<>(); queue.offer(0); for (int i = 1; i < n; i++) { // Prune indices that are too far while (!queue.isEmpty() && queue.peek() < i - maxJump) { queue.poll(); } // Check if there's a valid jump position and s[i] is '0' if (!queue.isEmpty() && s.charAt(i) == '0') { int prevIndex = queue.peek(); if (prevIndex <= i - minJump) { queue.offer(i); } } } // The last index must be reachable return !queue.isEmpty() && queue.peekLast() == n - 1; }}Complexity
Time
O(n). Each index of the string is processed once. It is also added to and removed from the deque at most once, leading to amortized O(1) time for deque operations per index.
Space
O(maxJump). The deque stores indices within the sliding window. The difference between the maximum and minimum index in the deque is at most `maxJump`. Therefore, the size of the deque is bounded by `maxJump`.
Trade-offs
Pros
Optimal time complexity of O(n).
Optimal space complexity, which is better than O(n) when
maxJumpis significantly smaller thann.
Cons
The logic involving the deque can be slightly more complex to grasp compared to the DP array-based solutions.
Solutions
Solution
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 ]; } }/** * @param {string} s * @param {number} minJump * @param {number} maxJump * @return {boolean} */ var canReach = function (s, minJump, maxJump) { const n = s.length; const pre = Array(n + 1).fill(0); pre[1] = 1; const f = Array(n).fill(false); f[0] = true; for (let i = 1; i < n; ++i) { if (s[i] === " 0 ") { const [l, r] = [Math.max(0, i - maxJump), 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]; };class Solution { public: bool canReach ( string s , int minJump , int maxJump ) { int n = s . size (); int pre [ n + 1 ]; memset ( pre , 0 , sizeof ( pre )); pre [ 1 ] = 1 ; bool f [ n ]; memset ( f , 0 , sizeof ( f )); f [ 0 ] = true ; for ( int i = 1 ; i < n ; ++ i ) { if ( s [ i ] == '0' ) { int l = max ( 0 , i - maxJump ); int r = i - minJump ; f [ i ] = l <= r && pre [ r + 1 ] - pre [ l ]; } pre [ i + 1 ] = pre [ i ] + f [ i ]; } return f [ n - 1 ]; } };class Solution : def canReach ( self , s : str , minJump : int , maxJump : int ) -> bool : n = len ( s ) pre = [ 0 ] * ( n + 1 ) pre [ 1 ] = 1 f = [ True ] + [ False ] * ( n - 1 ) for i in range ( 1 , n ): if s [ i ] == "0" : l , r = max ( 0 , i - maxJump ), i - minJump f [ i ] = l <= r and pre [ r + 1 ] - pre [ l ] > 0 pre [ i + 1 ] = pre [ i ] + f [ i ] return f [ - 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.