[Top Interview 150] 55. Jump Game

Solution)

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        # Initialization
        goal = len(nums) - 1

        # Check if current goal can be reached and update goal
        for i in range(len(nums)-2, -1, -1):
            if nums[i] + i >= goal:
                goal = i
        
        # Check if the end can be reached
        return True if goal == 0 else False

 
 
Problem: LeetCode
Reference: NeetCode
 
Time Complexity: O(n)
Space Complexity: O(1)

Explanation)

I used NeetCode's approach using a greedy algorithm to solve this problem. Check his video as well!
 
Instead of checking every jump from the beginning, we'll check from the end of nums.
We'll see if that goal (last index) is reachable from smaller indexes and update the goal to that smaller indexes. 
 
 

Initialization)

We need a variable that will keep updating goal points as we iterate nums.
Obviously, we want our initial goal to be the last index of nums because that's what our problem is asking for.
 

def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

 
 

Iteration)

Now we need to see if the smaller indexes can reach the goal.
 
Starting from -2nd index (Because -1st index is already our initial goal), we'll add the index with its value to find the max jump. If that max jump goes over the goal, that means the goal can be reached from that smaller index, so we'll update goal as that index.
 
As we have a new goal, we'll continue this process of searching a smaller index that can reach the new goal unti the 0th index.
 

def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums)-2, -1, -1):
            if nums[i] + i >= goal:
                goal = i

 
 

Return)

After the iteration, if the goal is updated as 0, that means there exists a path where the last index can be reached from 0th index. 
 
So, we'll return True if goal is 0 and False if goal is not zero.
 

def canJump(self, nums: List[int]) -> bool:
        goal = len(nums) - 1

        for i in range(len(nums)-2, -1, -1):
            # Update Goal
        
        return True if goal == 0 else False

 
 
 
I'm not sure why this is considered as an algorithm. Unlike two pointers or binary trees, it doesn't have a standard method to solve certain problems. It felt more like a condition where you try to solve a problem as soon as possible regardless of whether that solution is the most efficient way.