Leetcode 55: Jump Game

1. Problem Statement (Simple Explanation):

You’re given an integer array nums where:

• You start at index 0.

• Each nums[i] is the maximum jump length from position i.

From index i, you can jump to any index j such that: i < j <= i + nums[i]

You must determine:

• Return true if you can reach the last index (n - 1).

• Otherwise return false.

2. Examples:

Example 1:

Input: nums = [2,3,1,1,4]

Possible path:

• Start at index 0 (nums[0] = 2):

• Jump to index 1.

• From index 1 (nums[1] = 3):

• Jump directly to index 4 (last index).

You can reach the last index ⇒ true.

Output: true

Example 2:

Input: nums = [3,2,1,0,4]

• Start at index 0: can reach indices 1, 2, or 3.

• No matter what path you choose, eventually you end at index 3 (nums[3] = 0) → you cannot move further.

• Index 4 is unreachable.

Output: false

3. Approach – Greedy (O(n), Optimal):

We want to know if we can “cover” the path to the last index using jumps.

Maintain:

• farthest – the furthest index we can reach so far as we scan from left to right.

Algorithm:

1. Initialize farthest = 0.

2. Iterate i from 0 to n - 1:

• If i > farthest:

• It means we arrived at an index we cannot reach ⇒ return false.

• Update farthest = max(farthest, i + nums[i]).

• If farthest >= n - 1:

• We already can reach or pass the last index ⇒ return true.

3. If the loop ends, we can reach every visited index; farthest must be at least n - 1 ⇒ return true.

Why this works:

• At each step i, if i is reachable (i <= farthest), then from here we can reach up to i + nums[i].

• We greedily track the maximum reachable index.

• If we ever encounter i > farthest, it means the region beyond farthest is completely unreachable, so answer is false.

This is essentially checking if your reachable “frontier” reaches the end.

Pseudo-code:

Complexity:

Let n = len(nums):

• Time: O(n) – single pass.

• Space: O(1) – only a few variables.

4. Java code:

5. C code:

6. C++ code:

7. Python code:

8. JavaScript code: