DSA-141 · FOCUSED PRACTICE

Jump Game — Reachability

Intermediate · Java 21 · Version 1 · editorial draft

Java reference and baseline verified on JDK 21: 21849 deterministic checks. Learner drafts are not executed.

Understand the problem

Starting at index 0, determine whether you can reach the last index. nums[i] is the maximum forward jump length from i, and any distance from zero through that maximum is allowed.

Non-null int[] of 0–100,000 values, each 0–Integer.MAX_VALUE. Negative lengths are outside the contract.
Empty input returns false because no starting index exists. A one-element input returns true, even when its value is zero.
Return boolean and preserve input. Reaching or passing the final index suffices because a shorter permitted jump can land exactly there. Use long for i+nums[i].

Examples

Input: [2,3,1,1,4]
Output: true
Reach index 1, then jump to the final index.
Input: [3,2,1,0,4]
Output: false
The reachable prefix ends at the zero at index 3.
Input: [0]
Output: true
The starting index already is the target.

Before you start

Reachability versus minimum jumps
Overflow-safe interval extension

Recognize the structure

All jump lengths up to the maximum are allowed, so reachable positions form a continuous prefix. One farthest frontier summarizes all choices. If only exact jump lengths were allowed, this interval property would fail.

Your Java attempt

Java 21 · Draft only. Your code is not compiled, executed, or graded here. Run it locally against the examples and edge cases.

Saving stores text in this browser, visible to other people using this browser profile. It does not sync to your account. Loading is always explicit.

Approach, code, and test notes (20,000 characters maximum)

No unsaved text changes · 95/20,000 characters

Self-review

I rely on all shorter jumps being allowed.I never extend from an unreachable index.I distinguish feasibility from minimum jumps.

Use the checklist to test your explanation. Checks apply to this visit.

Try before revealing

Hint 1

Can reachable positions have a hole when every shorter jump is allowed?

Hint 2

Summarize all reachable positions by one frontier.

Hint 3

Fail on a gap; otherwise extend the frontier and stop when it covers the goal.

Derive the solution

Reveal the baseline, optimized reasoning, and Java code

Mark reachable positions by DP

Set reachable[0]=true and, for every reachable i, mark every forward j up to min(n-1,i+nums[i]). On [2,0,0], index 0 marks both later positions. Many overlapping ranges are repeatedly marked, producing O(n²) worst-case work and O(n) workspace.

Improve the baseline

Compress the reachable set

Because every shorter forward jump is permitted, reaching a far index also establishes every position between the start and that index as reachable.

Extend only from reachable positions

If i>farthest, a gap has been reached and no later starting point can help. Otherwise i can extend the frontier to max(farthest,i+nums[i]).

Stop as soon as the goal is covered

Once farthest≥n-1, the final index is reachable. Use long for the extension so a huge jump cannot wrap negative.

Why it is correct

Initialize

For nonempty input, index 0 is reachable, represented by frontier 0. Empty input is handled separately.

Preserve

Before examining i, every index through farthest is reachable using processed starting positions, plus the initial start. If i is within that interval, its allowed jumps add a contiguous range, extending the reachable prefix without holes. If it lies outside, no unprocessed later index is reachable from the existing prefix.

Finish

Covering n-1 proves success. Encountering a gap proves failure. Each index is examined at most once; if the scan ends, no remaining frontier extension can change the result.

Complete Java reference and baseline

Save as Solution.java. Node definitions and imports are included where needed. The baseline is included for comparison; respect its input-size limits.

public final class Solution {
    public static boolean canJump(int[] nums) {
        if (nums.length == 0) return false;
        long farthest = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i > farthest) return false;
            farthest = Math.max(farthest, (long) i + nums[i]);
            if (farthest >= nums.length - 1) return true;
        }
        return false;
    }

    public static boolean baseline(int[] nums) {
        if (nums.length == 0) return false;
        boolean[] reachable = new boolean[nums.length];
        reachable[0] = true;
        for (int i = 0; i < nums.length; i++) if (reachable[i]) {
            int end = (int) Math.min(nums.length - 1L, (long) i + nums[i]);
            for (int j = i + 1; j <= end; j++) reachable[j] = true;
        }
        return reachable[nums.length - 1];
    }
}

Read the meaningful blocks

Handle the empty universe

The usual index-0 initialization is invalid when no index exists.

Check accessibility before extending

An unreachable large jump cannot rescue the answer.

Widen before adding

(long)i+nums[i] avoids overflow; the frontier may safely exceed the array end.

Complexity

O(n) time and O(1) auxiliary space; early success or a gap may stop the scan sooner. Output is one boolean and input is preserved.

The explicit-reachability baseline uses O(n²) worst-case time and O(n) space. This greedy summary solves feasibility, not minimum jump count or path reconstruction.

Exact-state walkthroughs

Reveal normal and boundary traces

A blocked frontier

Input: [3,2,1,0,4] · Result: false

Step 1 of 7: Initialize the reachable prefix.

For nonempty input, index zero is reachable.

Original array indices and values

0: 3
1: 2
2: 1
3: 0
4: 4

State after this step
Variable	Value
nums	`[3,2,1,0,4]`
farthest	`0`

See the affected Java block

 1 public final class Solution {
 2     public static boolean canJump(int[] nums) {
 3         if (nums.length == 0) return false;
 4         long farthest = 0;
 5         for (int i = 0; i < nums.length; i++) {
 6             if (i > farthest) return false;
 7             farthest = Math.max(farthest, (long) i + nums[i]);
 8             if (farthest >= nums.length - 1) return true;
 9         }
10         return false;
11     }
12 
13     public static boolean baseline(int[] nums) {
14         if (nums.length == 0) return false;
15         boolean[] reachable = new boolean[nums.length];
16         reachable[0] = true;
17         for (int i = 0; i < nums.length; i++) if (reachable[i]) {
18             int end = (int) Math.min(nums.length - 1L, (long) i + nums[i]);
19             for (int j = i + 1; j <= end; j++) reachable[j] = true;
20         }
21         return reachable[nums.length - 1];
22     }
23 }
24

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize the reachable prefix.
For nonempty input, index zero is reachable.
nums
[3,2,1,0,4]
farthest
0
Extend only from a reachable index.
Every index through farthest is reachable under maximum-jump semantics.
i
0
before
0
jump
3
farthest
3
Extend only from a reachable index.
Every index through farthest is reachable under maximum-jump semantics.
i
1
before
3
jump
2
farthest
3
Extend only from a reachable index.
Every index through farthest is reachable under maximum-jump semantics.
i
2
before
3
jump
1
farthest
3
Extend only from a reachable index.
Every index through farthest is reachable under maximum-jump semantics.
i
3
before
3
jump
0
farthest
3
The next index lies beyond the reachable prefix.
No later unprocessed starting point can bridge this gap.
i
4
farthest
3
Return the contract result.
The final state satisfies the requested output contract.
result
false

Reach beyond the goal

Input: [2,0,0] · Result: true

Step 1 of 3: Initialize the reachable prefix.

For nonempty input, index zero is reachable.

Original array indices and values

0: 2
1: 0
2: 0

State after this step
Variable	Value
nums	`[2,0,0]`
farthest	`0`

See the affected Java block

 1 public final class Solution {
 2     public static boolean canJump(int[] nums) {
 3         if (nums.length == 0) return false;
 4         long farthest = 0;
 5         for (int i = 0; i < nums.length; i++) {
 6             if (i > farthest) return false;
 7             farthest = Math.max(farthest, (long) i + nums[i]);
 8             if (farthest >= nums.length - 1) return true;
 9         }
10         return false;
11     }
12 
13     public static boolean baseline(int[] nums) {
14         if (nums.length == 0) return false;
15         boolean[] reachable = new boolean[nums.length];
16         reachable[0] = true;
17         for (int i = 0; i < nums.length; i++) if (reachable[i]) {
18             int end = (int) Math.min(nums.length - 1L, (long) i + nums[i]);
19             for (int j = i + 1; j <= end; j++) reachable[j] = true;
20         }
21         return reachable[nums.length - 1];
22     }
23 }
24

Highlight locates the relevant statement or block; one trace step may summarize several assignments.

Read the full static trace

Initialize the reachable prefix.
For nonempty input, index zero is reachable.
nums
[2,0,0]
farthest
0
Extend only from a reachable index.
Every index through farthest is reachable under maximum-jump semantics.
i
0
before
0
jump
2
farthest
2
Return the contract result.
The final state satisfies the requested output contract.
result
true

Test the contract

Input: []
Output: false
No start.
Input: [0,1]
Output: false
Blocked at start.
Input: [2,0,0]
Output: true
A zero can be bypassed.
Input: [1,2147483647,0]
Output: true
Overflow-safe extension.

Common mistakes and counterexamples

Demand a jump equal to nums[i]

Counterexample: [2,0] is reachable by jumping one step.

Any shorter distance through the maximum is allowed.

Extend from an unreachable index

Counterexample: [0,5] cannot reach index 1.

Check i≤farthest first.

Assume any zero means failure

Counterexample: [2,0,0] reaches the end despite zeros.

Test whether a zero blocks the entire reachable frontier.

Allow index arithmetic to wrap

Counterexample: [1,MAX_VALUE,0] is reachable.

Use long for i+nums[i].

Follow-ups

Find the minimum number of jumps.

Track the end of the current reachable layer and the farthest next layer, incrementing jumps only at layer boundaries. Feasibility alone does not count jumps.

Return an actual path.

Record a predecessor when a newly covered position first becomes reachable, or derive boundary witnesses. State the O(n) extra memory and verify every chosen jump.

Allow only an exact jump length.

Reachability is no longer necessarily a prefix. Use explicit reachable states/graph traversal under the new rules instead of this greedy compression.

Related foundations

Greedy reasoning: justify compressed choices

Keep practicing

Return to the lesson

AceYourInterviews · 2026-10-14 · Original explanations, examples, and Java implementations for AceYourInterviews. Familiar task names identify standard algorithmic problems; no company-frequency claims are made.