LeetCode Solution 55 - Jump Game

Problem Statement

You are given an integer array nums. Each element in the array represents your maximum jump length from that position. Your goal is to determine if you can reach the last index starting from the first index.

Return true if you can reach the last index, otherwise return false.

Constraints:

• 1 <= nums.length <= 10^4
• 0 <= nums[i] <= 10^5

Optimal Approach - Greedy Algorithm

The most efficient way to solve this problem is by using the Greedy Algorithm.

Explanation:

1. Define a variable maxReach to track the farthest index we can reach.
2. Iterate through nums:
   • If i > maxReach, return false (we've hit an unreachable point).
   • Update maxReach as max(maxReach, i + nums[i]).
3. If we reach the last index or beyond, return true.

C++ Code (LeetCode-Compatible)

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (i > maxReach) return false;
            maxReach = max(maxReach, i + nums[i]);
        }
        return true;
    }
};

Step-by-Step Explanation

1. Initialize maxReach = 0.
2. Iterate through nums:
   • If i > maxReach, return false (unreachable index).
   • Update maxReach = max(maxReach, i + nums[i]).
3. Return true if we reach the last index or beyond.

Dry Run / Execution Steps

Example:

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

i	nums[i]	maxReach	Condition (i > maxReach)
0	2	2	False
1	3	4	False
2	1	4	False
3	1	4	False
4	4	8	False

Output: true

Alternative Approaches & Why Not?

Approach	Time Complexity	Space Complexity	Why Not?
Brute Force (Recursion)	Exponential $O(2^n)$	O(n)	Too slow for large inputs
Dynamic Programming (Top-Down Memoization)	O(n^2)	O(n)	Extra space and slower than greedy
Greedy (Best)	O(n)	O(1)	Fastest and optimal

Best Solution & Why It’s Best

The Greedy Algorithm is the best because:

1. Linear Time Complexity O(n).
2. Constant Space Complexity O(1).
3. Directly solves the problem in a single pass.

Complexity Analysis

• Time Complexity: O(n) (single pass through nums)
• Space Complexity: O(1) (no extra storage used)

Conclusion

• The best approach is Greedy Algorithm.
• Alternative approaches like Brute Force and Dynamic Programming are inefficient.
• Recommended practice problems:
  • Jump Game II (LeetCode 45)
  • Minimum Jumps to Reach Home (LeetCode 1654)
  • Frog Jump (LeetCode 403)