Problem

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.

Examples

Example 1

1
2
3
4
5

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

1
2

Input: s = "01101110", minJump = 2, maxJump = 3
Output: false

Similar Problems

Jump Game 1 - Check if it reaches last index Jump Game 2 - Get min jumps Jump Game 3 Jump Game 4 Jump Game 5 Jump Game 6 Minimum jumps to reduce number to 1

Solution

Method 1 - BFS

First, consider the standard BFS approach: use a queue to explore all indices reachable from the current position within the [curr_idx + minJump, curr_idx + maxJump] range, returning true if the end is reached.

However, since some indices may be revisited, it’s efficient to use a visited array or set to track which positions have already been processed and skip them in future traversals.

However this approach will result in TLE. Even with a set, previously processed indices may still be checked inside the inner loop, leading to a worst-case time complexity of O(n^2).

To prevent this, we can track the farthest index processed so far and always begin the next search from that point, updating this maximum index as we go.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public boolean canReach(String s, int minJump, int maxJump) {
	if(s.charAt(s.length() - 1) != '0')
		return false;
	
	Queue<Integer> queue = new LinkedList<>();
	boolean[] visited = new boolean[s.length()];
	queue.add(0);
	
	while(!queue.isEmpty()){
		int idx = queue.remove();
		if(idx == s.length() - 1)
			return true;
		for(int i = idx + minJump; i <= idx + maxJump && i < s.length(); i++){
			if(!visited[i] && s.charAt(i) == '0'){
				visited[i] = true;
				queue.add(i);
			}   
		}
	}
	
	return false;
}

Complexity

  • ⏰ Time complexity: O(n^2)
  • 🧺 Space complexity: O(n)

Method 2 – Optimized BFS with Sliding Window

Intuition

The main idea is to use BFS to explore reachable indices, but to avoid redundant work, we track the farthest index we’ve already processed. This prevents revisiting indices and ensures each index is processed only once, making the solution efficient.

Approach

  1. If the last character is not ‘0’, return false immediately.
  2. Initialize a queue with the starting index (0).
  3. Track the farthest index processed (maxReach).
  4. While the queue is not empty:
    • Pop the current index.
    • If it’s the last index, return true.
    • For each next index in [max(idx + minJump, maxReach), min(idx + maxJump, n-1)]:
      • If s[j] == '0', add j to the queue.
    • Update maxReach to the next index after the current window.
  5. If the end is never reached, return false.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
	 bool canReach(string s, int minJump, int maxJump) {
		  int n = s.size();
		  if (s[n - 1] != '0') return false;
		  queue<int> q;
		  q.push(0);
		  int maxReach = 1;
		  while (!q.empty()) {
				int i = q.front(); q.pop();
				for (int j = max(i + minJump, maxReach); j <= min(i + maxJump, n - 1); ++j) {
					 if (s[j] == '0') {
						  if (j == n - 1) return true;
						  q.push(j);
					 }
				}
				maxReach = max(maxReach, i + maxJump + 1);
		  }
		  return n == 1;
	 }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

func canReach(s string, minJump int, maxJump int) bool {
	 n := len(s)
	 if s[n-1] != '0' {
		  return false
	 }
	 q := []int{0}
	 maxReach := 1
	 for len(q) > 0 {
		  i := q[0]
		  q = q[1:]
		  for j := max(i+minJump, maxReach); j <= min(i+maxJump, n-1); j++ {
				if s[j] == '0' {
					 if j == n-1 {
						  return true
					 }
					 q = append(q, j)
				}
		  }
		  if maxReach < i+maxJump+1 {
				maxReach = i+maxJump+1
		  }
	 }
	 return n == 1
}

func min(a, b int) int { if a < b { return a }; return b }
func max(a, b int) int { if a > b { return a }; return b }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

class Solution {
	public boolean canReach(String s, int minJump, int maxJump) {
		if(s.charAt(s.length() - 1) != '0')
			return false;
		
		Queue<Integer> queue = new LinkedList<>();
		queue.add(0);
		
		// This variable tells us till which index we have processed
		int maxReach = 0;
		
		while(!queue.isEmpty()){
			int idx = queue.remove();
			// If we reached the last index
			if(idx == s.length() - 1)
				return true;
			
			// start the loop from max of [current maximum (idx + minJump), maximum processed index (maxReach)]
			for(int j = Math.max(idx + minJump, maxReach); j <= Math.min(idx + maxJump, s.length() - 1); j++){
				if(s.charAt(j) == '0')
					queue.add(j);
			}
			
			// since we have processed till idx + maxJump so update maxReach to next index
			maxReach = Math.min(idx + maxJump + 1, s.length() - 1);
		}
		
		return false;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
	 fun canReach(s: String, minJump: Int, maxJump: Int): Boolean {
		  val n = s.length
		  if (s[n - 1] != '0') return false
		  val q: ArrayDeque<Int> = ArrayDeque()
		  q.add(0)
		  var maxReach = 1
		  while (q.isNotEmpty()) {
				val i = q.removeFirst()
				for (j in maxOf(i + minJump, maxReach)..minOf(i + maxJump, n - 1)) {
					 if (s[j] == '0') {
						  if (j == n - 1) return true
						  q.add(j)
					 }
				}
				maxReach = maxOf(maxReach, i + maxJump + 1)
		  }
		  return n == 1
	 }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
	 def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
		  n: int = len(s)
		  if s[-1] != '0':
				return False
		  q: list[int] = [0]
		  max_reach: int = 1
		  while q:
				i: int = q.pop(0)
				for j in range(max(i + minJump, max_reach), min(i + maxJump, n - 1) + 1):
					 if s[j] == '0':
						  if j == n - 1:
								return True
						  q.append(j)
				max_reach = max(max_reach, i + maxJump + 1)
		  return n == 1
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

impl Solution {
	 pub fn can_reach(s: String, min_jump: i32, max_jump: i32) -> bool {
		  let n = s.len();
		  let s = s.as_bytes();
		  if s[n - 1] != b'0' { return false; }
		  let mut q = std::collections::VecDeque::new();
		  q.push_back(0);
		  let mut max_reach = 1;
		  while let Some(i) = q.pop_front() {
				let start = std::cmp::max(i + min_jump as usize, max_reach);
				let end = std::cmp::min(i + max_jump as usize, n - 1);
				for j in start..=end {
					 if s[j] == b'0' {
						  if j == n - 1 { return true; }
						  q.push_back(j);
					 }
				}
				max_reach = std::cmp::max(max_reach, i + max_jump as usize + 1);
		  }
		  n == 1
	 }
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)