LeetCode Solution 55 - Jump Game

Problem Statement

Given an array nums of length n, where nums[i] represents the maximum jump length from index i, determine if you can reach the last index.

Example 1:

Input: nums = [2,3,1,1,4]
Output: true
Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.

Example 2:

Input: nums = [3,2,1,0,4]
Output: false
Explanation: No matter what, you will reach index 3 and get stuck.

Optimal Approach: Greedy Algorithm

Idea

1. Track the farthest index you can reach.
2. Iterate over nums, updating the farthest reachable index.
3. If at any point, the current index is beyond the reachable range, return false.
4. If the farthest index reaches or exceeds n-1, return true.

C++ Code

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > maxReach) return false; // If stuck before reaching the end
            maxReach = max(maxReach, i + nums[i]);
            if (maxReach >= nums.size() - 1) return true;
        }
        return true;
    }
};

Step-by-Step Explanation

1. Initialize maxReach = 0 (tracks the farthest we can go).
2. Iterate through the array:
   • If i > maxReach, return false (we're stuck).
   • Update maxReach as max(maxReach, i + nums[i]).
   • If maxReach reaches n-1, return true.
3. If loop completes, return true (can reach the last index).

Dry Run

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

Index	nums[i]	maxReach Before	maxReach After	Can Move?
0	2	0	2	Yes
1	3	2	4	Yes
2	1	4	4	Yes
3	1	4	4	Yes
4	4	4	8 (end)	Yes

Output: true

Alternative Approaches

1. Brute Force (Backtracking)

• Try all paths recursively.
• Time Complexity: O(2^n) (exponential)
• Space Complexity: O(n) (recursion stack)
• ❌ Not feasible for large inputs.

2. Dynamic Programming (Bottom-Up)

• Use dp[i] to store if we can reach index i.
• Time Complexity: O(n^2) (nested loops)
• Space Complexity: O(n) (extra array)
• ❌ Too slow for large arrays.

Best Solution Comparison Table

Approach	Time Complexity	Space Complexity	Optimal?
Brute Force	O(2^n)	O(n)	❌
Dynamic Programming	O(n^2)	O(n)	❌
Greedy (Best)	O(n)	O(1)	✅

Complexity Analysis

• Time Complexity: O(n) (single pass through nums)
• Space Complexity: O(1) (only one variable maxReach)

Conclusion

The greedy approach is the best as it ensures O(n) runtime with O(1) space. The problem is similar to:

• Jump Game II
• Minimum Number of Jumps

Next Steps

• Try different variations of the problem to solidify concepts.
• Optimize using greedy patterns in other problems.

---

Hope this guide helps! 🚀 If you found this useful, check out similar problems on LeetCode. Happy coding!