1871. Jump Game VII
Problem Description
You are given a binary string s
that is 0-indexed, which means indexing starts from 0. Your task is to determine if you can move from the start position, index 0, to the last index of the binary string, s.length - 1
, using a set of movement rules defined by two integers minJump
and maxJump
. The conditions for moving from index i
to index j
are as follows:
- You can only jump to index
j
from indexi
ifi + minJump <= j <= min(i + maxJump, s.length - 1)
. - The destination index
j
must have a value of '0' in the binary string (s[j] == '0'
).
You can only start your movement from index 0 if its value is '0', and you must end at the last index s.length - 1
. The goal is to return true
if reaching the last index is possible under the given conditions, otherwise return false
.
Intuition
The essence of this problem is to find if there's a path from the beginning to the end of s
while obeying the jump constraints. One intuitive approach to solve this problem will be using dynamic programming, where we calculate the possibility of reaching a particular index based on the possibilities of reaching previous indices.
The solution hinges on the following intuitions:
- We should track reachability from the start to each index with a boolean array
dp
where each indexi
ofdp
signifies whether it is possible to reachs[i]
. - To efficiently determine if we can reach index
i
, we should use a prefix sum arraypre_sum
to quickly calculate the number of reachable indices in the range[i - maxJump, i - minJump]
without iterating through all of them every time. - If any index
j
within the range[i - maxJump, i - minJump]
is reachable (dp[j] == true
) ands[i] == '0'
, then indexi
is also reachable.
Thus, starting from index 0, we iteratively compute dp
and pre_sum
until we reach the end of the array or until it's clear that the end is not reachable. The last element of the dp
array gives us the answer to whether the end is reachable.
Learn more about Dynamic Programming, Prefix Sum and Sliding Window patterns.
Solution Approach
To implement the solution, we use dynamic programming combined with a prefix sum strategy. Here's a step-by-step breakdown of how the solution is composed:
-
First, initialize two arrays
dp
andpre_sum
with lengths equal ton
andn + 1
respectively, wheren
is the length of the binary strings
. The arraydp
will store boolean values indicating whether each indexi
is reachable from the start whilepre_sum
stores the prefix sums ofdp
. Setdp[0]
toTrue
because we start from index 0 and it's already reachable by definition. Similarly, setpre_sum[1]
to1
as we can reach the first element. -
Iterate through each character in the binary string starting from index 1 as we have already initialized index 0. On each iteration, check if the current character
s[i]
is '0'. If it's not, we can't possibly jump to this index anyway, so we move on. -
If
s[i]
is '0', check if there's any reachable index within the window defined by the current indexi
minusminJump
andmaxJump
. To do this quickly, we calculated the prefix sum up to indexi - minJump
and subtract it from the prefix sum up to indexi - maxJump
. If the resulting value is greater than 0, it means there is at least one reachable '0' we can jump from within the bounds. In this case, setdp[i]
toTrue
. -
Update the prefix sum array
pre_sum
accordingly by adding the value atdp[i]
to the prefix sum up to indexi
. -
Continue this process until you've gone through all characters of the binary string. The last element of the
dp
array,dp[n - 1]
, gives us the final answer. If it'sTrue
, that means the end of the string is reachable; otherwise, it is unreachable.
The key algorithms and data structures used in this approach are:
- Dynamic Programming (DP): Used to store the reachability state of each index as we progress through the string.
- Prefix Sum Array: Allows us to efficiently calculate the sum of elements in a range, which helps in quickly determining if a jump is possible without checking every individual index within the range each time.
By using the DP and Prefix Sum Array, we efficiently solve the problem by reusing the results of the sub-problems and avoiding redundant calculations. This way, each i
is checked only once, making the solution optimal in terms of time complexity.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider a small example to illustrate the solution. Suppose we have a binary string s = "0010110"
and the given jump rules are minJump = 2
and maxJump = 3
.
Step 0: Initialization
dp = [false, false, false, false, false, false, false]
pre_sum = [0, 0, 0, 0, 0, 0, 0, 0]
- We can start from index 0 since
s[0] == '0'
, sodp[0] = true
andpre_sum[1] = 1
.
Step 1: Checking each index
- Index
1
->s[1] == '0'
, but index1
cannot be reached directly from0
asminJump > 1
, sodp[1]
is not changed. - Index
2
->s[2] == '0'
and it's within theminJump
andmaxJump
from0
(0 + 2 <= 2 <= 0 + 3
). We find thatpre_sum[2 - 1 + 1] - pre_sum[2 - 3 + 1] = pre_sum[2] - pre_sum[0] = 1 - 0 = 1 > 0
, indicating that a previous index is reachable. So,dp[2] = true
andpre_sum[3] = pre_sum[2] + dp[2] = 1 + 1 = 2
. - Index
3
->s[3] == '1'
, so it can't be reached because the position does not contain '0'. - Index
4
->s[4] == '0'
. We can jump from both indices1
and2
to4
. However, sincedp[1]
is false anddp[2]
is true, we only consider the2
index. Again, we find thatpre_sum[4 - 2 + 1] - pre_sum[4 - 3 + 1] = pre_sum[3] - pre_sum[2] = 2 - 1 = 1 > 0
, sodp[4] = true
andpre_sum[5] = pre_sum[4] + dp[4] = 2 + 1 = 3
. - Index
5
->s[5] == '1'
, so it's not reachable. - Index
6
->s[6] == '0'
. It's reachable from index3
,4
withminJump
andmaxJump
rules. But sincedp[3]
is false, we only consider the4
. Checking thepre_sum
,pre_sum[6 - 2 + 1] - pre_sum[6 - 3 + 1] = pre_sum[5] - pre_sum[4] = 3 - 2 = 1 > 0
, sodp[6] = true
andpre_sum[7] = pre_sum[6] + dp[6] = 2 + 1 = 3
.
Step 2: Final Result
- Checking the last element in
dp
array,dp[6] = true
. This indicates that it's indeed possible to jump to the last index using the given rules. Thus, the function should return true for this test case.
The final dp
and pre_sum
look like this:
dp = [true, false, true, false, true, false, true]
pre_sum = [0, 1, 1, 2, 2, 3, 3, 3]
We've successfully found a path that allows us to travel from index 0
to index 6
, thereby adhering to the solution approach and confirming the possibility to reach the end index.
Solution Implementation
1class Solution:
2 def canReach(self, arr: str, min_jump: int, max_jump: int) -> bool:
3 # Length of the input string
4 length = len(arr)
5
6 # A dynamic programming list to keep track of the possibility to reach each index
7 can_reach = [False] * length
8
9 # The starting point is always reachable
10 can_reach[0] = True
11
12 # Prefix sum array to keep track of number of reachable points in the string up to index i
13 prefix_sum = [0] * (length + 1)
14
15 # Initially only the first point is reachable
16 prefix_sum[1] = 1
17
18 # Loop through each point in the string
19 for i in range(1, length):
20 # We only need to consider '0' positions since '1' positions are not reachable
21 if arr[i] == '0':
22 # Calculate the range of jumps
23 left_bound = max(0, i - max_jump) # Lower bound for the jump
24 right_bound = i - min_jump # Upper bound for the jump
25
26 # If the sum of reachable points between the bounds is greater than 0,
27 # then the current point is reachable
28 if right_bound >= left_bound and prefix_sum[right_bound + 1] - prefix_sum[left_bound] > 0:
29 can_reach[i] = True
30
31 # Update the prefix sum array with the reachability of the current index
32 prefix_sum[i + 1] = prefix_sum[i] + int(can_reach[i])
33
34 # Check if the last point is reachable, return the result
35 return can_reach[length - 1]
36
1class Solution {
2 public boolean canReach(String s, int minJump, int maxJump) {
3 // Get the length of the input string.
4 int length = s.length();
5
6 // Create a dynamic programming (dp) array to hold the reachability of each position.
7 boolean[] isReachable = new boolean[length];
8
9 // Always start at position 0.
10 isReachable[0] = true;
11
12 // Use a prefix sum array to keep a running sum of reachable positions.
13 int[] prefixSum = new int[length + 1];
14 prefixSum[1] = 1;
15
16 // Iterate through the string starting at position 1 since we're always starting at position 0.
17 for (int i = 1; i < length; ++i) {
18 // Check if the current position has a '0' and therefore can be landed on.
19 if (s.charAt(i) == '0') {
20 // Calculate the maximum left (furthest back we can jump from current position).
21 int left = Math.max(0, i - maxJump);
22 // Calculate the minimum right (closest jump we can make to current position).
23 int right = i - minJump;
24
25 // Ensure that right is not less than left and that there is at least one true
26 // within the range in the prefix sum array to jump to current position.
27 if (right >= left && prefixSum[right + 1] - prefixSum[left] > 0) {
28 // Mark the current position as reachable.
29 isReachable[i] = true;
30 }
31 }
32
33 // Update the prefix sum array with the sum up to the current position.
34 prefixSum[i + 1] = prefixSum[i] + (isReachable[i] ? 1 : 0);
35 }
36
37 // Return if the last position in the string is reachable.
38 return isReachable[length - 1];
39 }
40}
41
1#include <vector>
2#include <string>
3
4/**
5 * Function to determine if it's possible to reach the end of a string by jumping
6 * between the positions specified by min_jump and max_jump.
7 * Each jump can only be made if the destination is a '0' character in the string.
8 *
9 * @param s The string representing safe ('0') and unsafe ('1') positions.
10 * @param min_jump The minimum length of a jump.
11 * @param max_jump The maximum length of a jump.
12 * @return boolean indicating whether the end of the string can be reached.
13 */
14bool canReach(const std::string& s, int min_jump, int max_jump) {
15 int n = s.length(); // Length of the string
16 std::vector<int> dp(n, 0); // DP array to store whether a position is reachable
17 std::vector<int> prefix_sum(n + 1, 0); // Array to store the prefix sum of the DP
18
19 dp[0] = 1; // Starting position is always reachable
20 prefix_sum[1] = 1; // Initialize prefix sum
21
22 // Iterate through the string to fill the DP array with reachable positions
23 for (int i = 1; i < n; i++) {
24 // Check if the current position is '0' and can potentially be jumped to
25 if (s[i] == '0') {
26 int left_bound = std::max(0, i - max_jump); // Left boundary for the window from which we can jump
27 int right_bound = i - min_jump; // Right boundary for the window from which we can jump
28
29 // If there is at least one reachable position within the window, mark the current position as reachable
30 if (left_bound <= right_bound && prefix_sum[right_bound + 1] - prefix_sum[left_bound] > 0) {
31 dp[i] = 1;
32 }
33 }
34 // Update the prefix sum array with the current reachability status
35 prefix_sum[i + 1] = prefix_sum[i] + dp[i];
36 }
37
38 // Return if the last position is reachable
39 return dp[n - 1] == 1;
40}
41
42// Example usage:
43/*
44int main() {
45 bool result = canReach("011010", 2, 3);
46 std::cout << (result ? "true" : "false") << std::endl; // Expected output: true or false
47 return 0;
48}
49*/
50
1// Function to determine if it's possible to reach the end of a string by jumping
2// between the positions specified by minJump and maxJump.
3// Each jump can only be made if the destination is a '0' character in the string.
4/**
5 * @param s The string representing safe(0) and unsafe(1) positions.
6 * @param minJump The minimum length of a jump.
7 * @param maxJump The maximum length of a jump.
8 * @returns boolean indicating whether the end of the string can be reached.
9 */
10const canReach = (s: string, minJump: number, maxJump: number): boolean => {
11 const n: number = s.length; // Length of the string
12 let dp: number[] = new Array(n).fill(0); // DP array to store whether a position is reachable
13 let prefixSum: number[] = new Array(n + 1).fill(0); // Array to store the prefix sum of the DP
14
15 dp[0] = 1; // Starting position is always reachable
16 prefixSum[1] = 1; // Initialize prefix sum
17
18 // Iterate through the string to fill the DP array with reachable positions
19 for (let i = 1; i < n; i++) {
20 // Check if the current position is '0' and can potentially be jumped to
21 if (s.charAt(i) === '0') {
22 let leftBound = Math.max(0, i - maxJump); // Left boundary for the window from which we can jump
23 let rightBound = i - minJump; // Right boundary for the window from which we can jump
24
25 // If there is at least one reachable position within the window, mark current position as reachable
26 if (leftBound <= rightBound && prefixSum[rightBound + 1] - prefixSum[leftBound] > 0) {
27 dp[i] = 1;
28 }
29 }
30 // Update the prefix sum array with current reachability status
31 prefixSum[i + 1] = prefixSum[i] + dp[i];
32 }
33
34 // Return if the last position is reachable
35 return dp[n - 1] === 1;
36};
37
38// Example usage:
39// const result: boolean = canReach("011010", 2, 3);
40// console.log(result); // Expected output: true or false
41
Time and Space Complexity
The given Python code implements a dynamic programming solution to determine if it is possible to reach the end of a string given certain jumping rules.
Time Complexity
The time complexity of the algorithm can be analyzed based on loop operations and array manipulations:
- Initialization of the
dp
andpre_sum
arrays withFalse
and0
respectively, which takesO(n)
time each, wheren
is the length of the input string. - A single for-loop on the index
i
ranges from1
ton-1
, resulting inO(n)
iterations. - Inside the for-loop, the check
pre_sum[r + 1] - pre_sum[l] > 0
is a constant time operation, O(1), as it involves accessing elements of the prefix sum array and subtraction. - The update of the
pre_sum
array withpre_sum[i + 1] = pre_sum[i] + dp[i]
is also a constant time operation, executed once each loop iteration.
Combining these observations, the overall time complexity can be considered as O(n)
because the for-loop dominates the execution time.
Space Complexity
The space complexity is determined by the space required to store the dynamic programming states and additional constructs:
- The
dp
array that stores Boolean values representing if a positioni
can be reached, has a size ofn
, contributingO(n)
to the space complexity. - The
pre_sum
array helps keep track of the prefix sums ofdp
, also requiringO(n)
space.
Hence, the overall space complexity of this solution is O(n)
, which is a sum of space used by dp
and pre_sum
.
In conclusion, the given code has a time complexity of O(n)
and a space complexity of O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which algorithm should you use to find a node that is close to the root of the tree?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
https algomonster s3 us east 2 amazonaws com cover_photos stack svg Sliding Window Maximum Monotonic Stack We have an array and a sliding window defined by a start index and an end index The sliding window moves from left of the array to right There are always k elements in
Want a Structured Path to Master System Design Too? Donāt Miss This!