Jump Game VII
The briefingthe full drill, in my own words
The drill: On a strip of '0's and '1's, start at the front — always a '0' — and hop only onto other '0' cells. Each hop's length must fall inside a fixed [min, max] range. Decide whether the far end is reachable.
This site verifies the drill as a hop across a strip of '0' and '1' cells: the starting cell at index zero is always a '0', and every hop must land on a '0' cell too — landing on a '1' is never allowed.
Every hop's length has to fall within a fixed [minJump, maxJump] window measured in index positions — nothing shorter, nothing longer, regardless of how far a '0' cell might otherwise sit.
The question is whether some chain of such hops, starting at the front, can ever land exactly on the strip's final index.
- the strip's first and last characters are always '0'
- every hop lands only on '0' cells; '1' cells are never valid landings
- hop length must fall between minJump and maxJump inclusive, every time
- hops always move forward toward the end of the strip
The hintstake only what you need
HINT 1 THE NUDGE
From each landing spot, trying every jump length in [minJump, maxJump] one at a time re-derives the same reachability fact over and over for overlapping windows. What does 'is position i reachable' actually depend on?
HINT 2 THE STRUCTURE
Position i is reachable exactly when s[i] is '0' AND some already-reachable position falls in the window [i − maxJump, i − minJump]. That's a range question, not an all-pairs question.
HINT 3 ONE STEP FROM THE ANSWER
Keep a running prefix count of reachable positions. Position i is reachable when s[i] == '0' and the reachable-count inside [i − maxJump, i − minJump] is nonzero — one subtraction of two prefix sums, O(1) per position.
Coach's boardthe pattern, step by step
Strip "011010", hops must land on '0' and span between minJump=2 and maxJump=3. Index 0 is reachable — that's the start.
The splitstwo paces, two languages
class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
dp = [False] * n
dp[0] = True
prefix = [0] * (n + 1)
prefix[1] = 1 # dp[0] is reachable
for i in range(1, n):
lo = max(0, i - maxJump)
hi = i - minJump
if s[i] == "0" and hi >= lo and prefix[hi + 1] - prefix[lo] > 0:
dp[i] = True
prefix[i + 1] = prefix[i] + (1 if dp[i] else 0)
return dp[n - 1]class Solution:
def canReach(self, s: str, minJump: int, maxJump: int) -> bool:
n = len(s)
dp = [False] * n
dp[0] = True
for i in range(1, n):
if s[i] != "0":
continue
lo = max(0, i - maxJump)
hi = i - minJump
for j in range(lo, hi + 1):
if 0 <= j < i and dp[j]:
dp[i] = True
break
return dp[n - 1]class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
boolean[] dp = new boolean[n];
dp[0] = true;
int[] prefix = new int[n + 1];
prefix[1] = 1; // dp[0] is reachable
for (int i = 1; i < n; i++) {
int lo = Math.max(0, i - maxJump);
int hi = i - minJump;
if (s.charAt(i) == '0' && hi >= lo && prefix[hi + 1] - prefix[lo] > 0) {
dp[i] = true;
}
prefix[i + 1] = prefix[i] + (dp[i] ? 1 : 0);
}
return dp[n - 1];
}
}class Solution {
public boolean canReach(String s, int minJump, int maxJump) {
int n = s.length();
boolean[] dp = new boolean[n];
dp[0] = true;
for (int i = 1; i < n; i++) {
if (s.charAt(i) != '0') {
continue;
}
int lo = Math.max(0, i - maxJump);
int hi = i - minJump;
for (int j = lo; j <= hi; j++) {
if (j >= 0 && j < i && dp[j]) {
dp[i] = true;
break;
}
}
}
return dp[n - 1];
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED