Jump Game I and II
Determine reachability and minimum jumps using a greedy range-expansion approach that avoids the need for DP.
Jump Game I and II is a free DSA Interview Prep lesson on CoddyKit — lesson 3 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the DSA Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Jump Game I: Can You Reach the End?
Jump Game I (LeetCode 55): given an array where nums[i] is the maximum jump length from index i, determine if you can reach the last index starting from index 0. For [2, 3, 1, 1, 4], you can reach the end (jump 2→3, then 3 gets you to end). For [3, 2, 1, 0, 4], you cannot (always land on 0, which has a jump of 0). A greedy solution runs in O(n).
# Can you reach the last index?
nums1 = [2, 3, 1, 1, 4] # True: 0→1→4 or 0→2→3→4
nums2 = [3, 2, 1, 0, 4] # False: always land on index 3 (value 0)
# At index 3 (value 0): no matter how you get here,
# you can't jump further to reach index 4
print('nums1 last index:', len(nums1)-1)
print('nums2 index 3 jump value:', nums2[3]) # 0 = stuckGreedy: Track Maximum Reach
The greedy insight for Jump Game I: maintain max_reach, the farthest index reachable so far. At each index i, update max_reach = max(max_reach, i + nums[i]). If at any point i > max_reach, the current index is unreachable — return False. If we reach or pass the last index, return True. No DP or backtracking needed.
def can_jump(nums):
max_reach = 0
for i, jump in enumerate(nums):
if i > max_reach: # can't reach index i
return False
max_reach = max(max_reach, i + jump)
if max_reach >= len(nums) - 1:
return True # early exit
return True
print(can_jump([2, 3, 1, 1, 4])) # True
print(can_jump([3, 2, 1, 0, 4])) # False
print(can_jump([0])) # True (already at last index)
print(can_jump([1, 0, 0])) # FalseTracing Jump Game I
Trace [3, 2, 1, 0, 4]: i=0, jump=3, max_reach=3. i=1, jump=2, max_reach=max(3,3)=3. i=2, jump=1, max_reach=max(3,3)=3. i=3, jump=0, max_reach=max(3,3)=3. i=4, i=4 > max_reach=3 → return False. The algorithm correctly identifies that index 4 is unreachable. Every path from index 0 is trapped because the 0 at index 3 limits max_reach to 3.
def can_jump_trace(nums):
max_reach = 0
for i, jump in enumerate(nums):
print(f'i={i}, jump={jump}, max_reach before={max_reach}', end='')
if i > max_reach:
print(' → UNREACHABLE')
return False
max_reach = max(max_reach, i + jump)
print(f' → max_reach={max_reach}')
return True
print('Result:', can_jump_trace([3, 2, 1, 0, 4]))Jump Game II: Minimum Jumps
Jump Game II (LeetCode 45) asks for the minimum number of jumps to reach the last index (always reachable). The greedy approach uses a range expansion strategy: maintain the current jump's farthest reach (curr_end) and the next jump's farthest reach (farthest). When you exhaust the current jump's range, you must make a jump — increment jumps and set curr_end = farthest.
def jump(nums):
n = len(nums)
if n == 1: return 0 # already at destination
jumps = 0
curr_end = 0 # end of current jump's range
farthest = 0 # farthest reachable in next jump
for i in range(n - 1): # don't jump from last index
farthest = max(farthest, i + nums[i])
if i == curr_end: # exhausted current jump range
jumps += 1
curr_end = farthest
if curr_end >= n - 1: break
return jumps
print(jump([2, 3, 1, 1, 4])) # 2 (0→1→4)
print(jump([2, 3, 0, 1, 4])) # 2 (0→1→4)
print(jump([1, 2, 1, 1, 1])) # 3Visualising Jump Game II
Think of Jump Game II as a BFS level-by-level approach without the queue overhead. Each jump corresponds to a BFS level. curr_end is the boundary of the current level. farthest is the maximum index reachable in the next level. When you finish scanning the current level (i == curr_end), you've determined the next level's boundary and must increment the jump count. This is BFS on an implicit graph in O(n) time and O(1) space.
def jump_traced(nums):
n = len(nums)
jumps = curr_end = farthest = 0
for i in range(n - 1):
farthest = max(farthest, i + nums[i])
print(f'i={i}: farthest={farthest}, curr_end={curr_end}')
if i == curr_end:
jumps += 1
curr_end = farthest
print(f' → JUMP #{jumps}, new range ends at {curr_end}')
if curr_end >= n - 1: break
return jumps
print('Min jumps:', jump_traced([2, 3, 1, 1, 4]))Why Greedy is Correct for Jump II
Why does greedy (always extend to farthest) give the minimum jumps? Exchange argument: suppose the optimal solution makes a jump that doesn't reach the farthest point. We can always extend that jump to reach farthest without any extra cost — it's still one jump. By always taking the maximum range per jump, we guarantee the minimum number of jumps needed. Any solution that takes less range per jump cannot do better and would need more jumps to cover the same distance.
# Correctness verification: compare to BFS
from collections import deque
def jump_bfs(nums):
n = len(nums)
if n == 1: return 0
visited = [False] * n
visited[0] = True
queue = deque([0])
level = 0
while queue:
level += 1
for _ in range(len(queue)):
pos = queue.popleft()
for j in range(1, nums[pos] + 1):
nxt = pos + j
if nxt >= n - 1: return level
if not visited[nxt]:
visited[nxt] = True
queue.append(nxt)
return -1
# Both should give same results
for nums in [[2,3,1,1,4],[2,3,0,1,4],[1,2,1,1,1]]:
print(jump(nums), '==', jump_bfs(nums))DP Alternative for Jump Game II
A DP solution: dp[i] = minimum jumps to reach index i. For each position j, update all reachable positions: dp[j+k] = min(dp[j+k], dp[j]+1) for k in 1..nums[j]. This runs in O(n × max_jump) time and O(n) space — much slower than the O(n) greedy. The greedy is superior here; DP is shown for comparison to illustrate how greedy can avoid the inner loop.
def jump_dp(nums):
n = len(nums)
dp = [float('inf')] * n
dp[0] = 0
for j in range(n):
for k in range(1, nums[j] + 1):
if j + k < n:
dp[j+k] = min(dp[j+k], dp[j] + 1)
return dp[n-1]
print(jump_dp([2, 3, 1, 1, 4])) # 2
print(jump_dp([1, 2, 1, 1, 1])) # 3
# Greedy is O(n), DP is O(n * max_jump)
# For large inputs with big jump values, greedy is much fasterJump Game III: Reach Index Zero
Jump Game III (LeetCode 1306): start at a given index; from index i, jump to i + nums[i] or i - nums[i]. Can you reach any index with value 0? This is a reachability problem (BFS/DFS), not a minimisation problem — greedy does not apply. Use BFS with a visited set to avoid cycles. Time: O(n).
from collections import deque
def can_reach(arr, start):
n = len(arr)
visited = set()
queue = deque([start])
while queue:
idx = queue.popleft()
if arr[idx] == 0: return True
if idx in visited: continue
visited.add(idx)
for nxt in [idx + arr[idx], idx - arr[idx]]:
if 0 <= nxt < n and nxt not in visited:
queue.append(nxt)
return False
print(can_reach([4,2,3,0,3,1,2], 5)) # True (5→4→1→3, arr[3]=0)
print(can_reach([3,0,2,1,2], 2)) # False (can't reach index 1, arr[1]=0)Jump Game VII: Reachable with Range
Jump Game VII (LeetCode 1871): can you traverse a binary string jumping from index 0 to the last index, where from position i you can jump to any '0' in [i+minJump, i+maxJump]? Use a sliding window sum over the reachable array. Maintain a prefix sum of reachable positions; a position j is reachable if there is a reachable position in [j-maxJump, j-minJump].
def can_reach_vii(s, min_jump, max_jump):
n = len(s)
reach = [False] * n
reach[0] = True
pre = [0] * (n + 1) # prefix sum of reachable positions
pre[1] = 1
for j in range(1, n):
# Window sum: any reachable position in [j-maxJump, j-minJump]?
lo = max(0, j - max_jump)
hi = max(0, j - min_jump + 1)
window_sum = pre[hi] - pre[lo]
if s[j] == '0' and window_sum > 0:
reach[j] = True
pre[j+1] = pre[j] + (1 if reach[j] else 0)
return reach[n-1]
print(can_reach_vii('011010', 2, 3)) # True
print(can_reach_vii('01101110', 2, 3)) # FalseComparing Greedy and BFS Solutions
Jump Game II has two equivalent O(n) approaches: greedy range expansion and BFS level traversal. The greedy approach uses O(1) space (no queue), while BFS uses O(n) for the visited set. In an interview, greedy is preferred for its space efficiency. However, BFS is easier to derive first — if you struggle to see the greedy solution, code BFS to get a working solution and then optimise. Both correctly compute the minimum number of jumps.
# Both approaches are O(n) time
# Greedy: O(1) space — preferred in interviews
# BFS: O(n) space — easier to derive
# Greedy advantage: no auxiliary data structures
def jump_greedy(nums):
n, jumps, curr, far = len(nums), 0, 0, 0
for i in range(n-1):
far = max(far, i+nums[i])
if i == curr: jumps += 1; curr = far
return jumps
# BFS equivalence: each level = one jump
from collections import deque
def jump_bfs(nums):
n = len(nums)
if n == 1: return 0
q, visited, level = deque([0]), {0}, 0
while q:
level += 1
for _ in range(len(q)):
pos = q.popleft()
for j in range(1, nums[pos]+1):
nxt = pos + j
if nxt >= n-1: return level
if nxt not in visited: visited.add(nxt); q.append(nxt)
return -1
nums = [2,3,1,1,4]
print(jump_greedy(nums), '==', jump_bfs(nums)) # both 2Jump Game Complexity Summary
Complexity summary across Jump Game variants: Jump I (reachability): O(n) time, O(1) space. Jump II (min jumps greedy): O(n) time, O(1) space. Jump II (BFS): O(n) time, O(n) space. Jump II (DP): O(n × max_jump) time, O(n) space. Jump III (BFS/DFS): O(n) time, O(n) space for visited. Jump VII (sliding window): O(n) time, O(n) space. Always present the greedy O(n) O(1) solution for Jump I and II in interviews.
# Comparison: all versions on the same input
nums = [2, 3, 1, 1, 4]
# Jump I
def can_jump(nums):
mr = 0
for i, j in enumerate(nums):
if i > mr: return False
mr = max(mr, i+j)
return True
# Jump II greedy O(n) O(1)
def jump_min(nums):
n, jumps, curr, far = len(nums), 0, 0, 0
for i in range(n-1):
far = max(far, i+nums[i])
if i == curr:
jumps += 1; curr = far
if curr >= n-1: break
return jumps
print('Can reach:', can_jump(nums)) # True
print('Min jumps:', jump_min(nums)) # 2
print('Complexity: O(n) time, O(1) space')Quick Check
Test your understanding of Data Structures & Algorithms — Coding Interview Prep concepts from this lesson.
Lesson Recap
In this lesson you learned: Jump Game I uses greedy max_reach tracking to determine reachability in O(n) time O(1) space, Jump Game II uses range expansion with curr_end and farthest to count minimum jumps in O(n) O(1), and the greedy range expansion is equivalent to level-by-level BFS without the queue overhead. Next up we apply greedy reasoning to the Task Scheduler cooling period and the Gas Station circular feasibility problems.
Frequently asked questions
Is the “Jump Game I and II” lesson free?
Yes — the full text of “Jump Game I and II” is free to read here on the web, and the DSA Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the DSA Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Jump Game I and II”?
Determine reachability and minimum jumps using a greedy range-expansion approach that avoids the need for DP. You practise DSA Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start DSA Interview Prep?
No prior experience is required. DSA Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 3 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Jump Game I and II” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this DSA Interview Prep lesson?
Yes. Every DSA Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.