55. Jump Game

📝 Problem Details

• Title: 55. Jump Game
• Link: https://leetcode.com/problems/jump-game/
• Difficulty: Medium
• Tags/Categories: Greedy

input array nums starting position at the first index of nums 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

💭What Were My Initial Thoughts?

what if we greedily take the larger jump each turn
[2  3  1  1  4]
[0] --> 2 spaces --> [2]
[2] --> 1 space --> [3]
[3] --> 1 space --> [4] (reached the end)

while this greedy approach works for this specific case, this wont work for cases where we skip over the optimal path in prioritization of a larger initial step, which may lead to a bad path
----

what if we start from the finish point, and work our way backwards
check if the index before it can reach the target, change the target value each time a successful jump is encountered

💡 Explanation of Solution

1. start from the last index (destination)
2. try to find the leftmost index (i) that can jump to the current destination
3. if we find such an index, move destination to i
4. repeat until the destination is 0

⌛ Complexity Analysis

Time Complexity: O(n)
Space Complexity: O(1)

💻 Implementation of Solution

class Solution {
public:
    bool canJump(vector<int>& nums) {
        int goal = nums.size()-1; // start from the last index
 
        for(int i = nums.size()-2; i >= 0; i--) { // iterate backward
            if(i + nums[i] >= goal) { // can we jump to or past goal?
                goal = i;
            }
        }
        return goal == 0; // if we can reach idnex 0, return true
    }
};