Jump Game

Practice here

You are given an integer array nums. You are initially positioned at the array's first index, and each element in the array represents your maximum jump length at that position.

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

Recursion Approach#

• Intuition: From any index, try every possible jump length from 1 to nums[idx]. If any recursive path reaches the last index, return true. This explores all reachable sequences exhaustively.
• Mechanics: Base cases: return false if idx is out of bounds, return true if idx equals the last index. Otherwise, loop over all jump sizes and recurse — the first successful branch short-circuits via the if check.
• Trade-off: Exponential O(2^n) time due to recomputing reachability for the same indices multiple times. Memoization would reduce it to O(n²), and the greedy approach reduces it further to O(n) with O(1) space.

class Solution {
public:
    bool canJumpUtil(vector<int>& nums, int idx)
    {
        if(idx>=nums.size())
            return false;
        if(idx==nums.size()-1)
            return true;

        for(int i=1;i<=nums[idx];i++){
            if(canJumpUtil(nums, idx+i))
                return true;   
        }
        return false;
    }

    bool canJump(vector<int>& nums) {
        return canJumpUtil(nums, 0);
    }
};

Time Complexity: O(2ⁿ) -> TLE

Space Complexity: O(n)

Greedy Approach#

• Intuition: Track the farthest index reachable at any point (maxReach). If the current index ever exceeds maxReach, there is a gap — no jump from any earlier position can bridge it, so the last index is unreachable. Otherwise, continuously extend maxReach and return true when the scan completes.
• Mechanics: Iterate left to right; at each index i, first check i > maxReach (stuck in a gap → false), then update maxReach = max(maxReach, i + nums[i]). If the loop finishes, every index was reachable and true is returned.
• Trade-off: A single O(n) pass with no extra space. The greedy "always extend the frontier" choice is optimal because knowing the farthest reachable index at every step is sufficient — you never need to know which specific path was taken to get there.

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;
    }
};

Time Complexity: O(n)

Space Complexity: O(1)