Problem Statement

You are given an integer array nums, where nums[i] represents the maximum number of steps you can jump forward from index i.

You start at the first index of the array.

Your task is to determine whether you can reach the last index.

Return true if the last index is reachable; otherwise, return false.

Problem Link -: Jump Game

Example 1

One possible sequence is:

From index 0, we can jump up to 2 positions.

From index 1, we can jump up to 3 positions, which allows us to reach the last index.

Example 2

We can reach index 3, but:

Therefore, we cannot move any further and the last index cannot be reached.

Understanding the Problem

The important thing to understand is that we do not need to find the exact sequence of jumps.

We only need to answer:

"How far can I reach from all the positions I have been able to reach so far?"

For example:

Initially, we are at index 0.

Since:

we can reach:

So our current farthest reachable index is:

When we reach index 1, it allows us to jump 3 positions.

Therefore:

Now we can reach index 4, which is the last index.

The key idea is therefore to continuously maintain the farthest index we can reach.

Greedy Approach

We maintain a variable:

which represents the farthest index that we can currently reach.

Initially:

At every index i, we first check:

If:

then index i is unreachable.

That means the answer must be:

Otherwise, index i is reachable, so we can use its jump length to potentially extend our reachable range.

The new farthest position becomes:

In Java:

If this reaches the last index, we can immediately return true.

Java Solution

Step-by-Step Explanation

Let's break the important part of the algorithm down.

1. Start with the first reachable position

If:

then from index 0, we can initially reach index 2.

So:

2. Iterate through the array

We examine every index that we potentially can reach.

3. Check whether the current index is reachable

Suppose:

This means:

We can only reach up to index 3, so index 4 is unreachable.

There is no way to continue.

Therefore:

4. Extend the reachable range

If the current index is reachable, we calculate how far we can jump from it:

But this might not necessarily be better than our existing reachable position.

Therefore we take the maximum:

This is the core greedy step.

Dry Run

Consider:

Initially:

Now iterate.

i = 1

Current reachable range:

Can we reach index 1?

Yes.

From index 1:

Update:

Since:

we can reach the last index.

Therefore:

Another Dry Run: Impossible Case

Consider:

Initially:

i = 1

Reachable.

From index 1:

So:

i = 2

Reachable.

So:

i = 3

Reachable.

But:

We are still stuck at:

i = 4

Now:

Index 4 cannot be reached.

Therefore:

Why Does the Greedy Approach Work?

The important observation is that we don't care which particular jump we take.

We care only about the farthest position that can be reached from the positions already available to us.

Suppose we can reach index i.

From there, we can reach:

If this is farther than our previous maximum, we update our reachable boundary.

Therefore, at every step:

contains all the information we need.

We don't need to remember every possible path.

This is what makes the solution greedy rather than recursive or dynamic programming based.

Why Not Try Every Possible Jump?

A straightforward recursive approach might try:

The number of possible paths can grow very quickly.

We don't actually need to explore these paths.

For example, if we can reach:

and:

we don't need to separately remember both paths.

What matters is simply:

That removes a huge amount of unnecessary work.

A Slightly Cleaner Version

The same greedy logic can be written using a more descriptive variable name:

Here:

makes the purpose of the variable clearer than j.

The logic is exactly the same.

Complexity Analysis

Let n be the length of the array.

Time Complexity

We traverse the array only once:

Space Complexity

We use only a few variables:

So the final complexity is:

Important Edge Cases

1. Array contains only one element

We are already at the last index.

Answer:

2. First position cannot move

We cannot reach index 1.

Answer:

3. Last index is directly reachable

The first position can jump directly to the end.

Answer:

4. Zeros in the middle

Zeros are not necessarily a problem.

For example:

We can jump from index 0 directly to index 2.

So the answer is:

A zero only becomes a problem when it prevents our reachable boundary from extending far enough.

Key Takeaway

The most important idea behind Jump Game is:

Don't try to decide which jump to make. Track how far you can reach.

At every index:

1. Check whether the index is reachable.
2. Calculate how far this index can take us.
3. Update the farthest reachable position.
4. If the last index becomes reachable, return true.
5. If we encounter an index beyond the reachable boundary, return false.

The pattern can be summarized as:

This is a classic example of a Greedy Array Traversal problem and is an important pattern to recognize in coding interviews.

Final Complexity

The greedy solution is optimal because we only need to maintain the farthest position reachable at each point rather than exploring every possible jump sequence.