leetcode-55 Jump Game

# 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.
#
# 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: You will always arrive at index 3. Its maximum jump length is 0,
# which makes it impossible to reach the last index.
#
# Constraints:
# 1 <= nums.length <= 10^4
# 0 <= nums[i] <= 10^5

class Solution:
    # Approach 1: Greedy - Forward tracking
    def canJump(self, nums: List[int]) -> bool:
        max_reach = 0

        for i in range(len(nums)):
            # If current position is beyond max reachable, can't proceed
            if i > max_reach:
                return False

            # Update max reachable position
            max_reach = max(max_reach, i + nums[i])

            # Early termination: if we can reach the end
            if max_reach >= len(nums) - 1:
                return True

        return True

    # Approach 2: Greedy - Backward tracking (cleaner)
    def canJump2(self, nums: List[int]) -> bool:
        # Start from the last position
        # Track the leftmost position that can reach the goal
        goal = len(nums) - 1

        for i in range(len(nums) - 2, -1, -1):
            # If current position can reach goal
            if i + nums[i] >= goal:
                goal = i  # Update goal to current position

        # If goal is at start, we can reach the end
        return goal == 0

# Time Complexity: O(n)
# Space Complexity: O(1)
#
# Greedy Strategy:
# Forward: Track maximum reachable position at each step
# Backward: Track leftmost position that can reach the end
#
# Key Insight: We don't need to explore all paths (like DP/backtracking)
# Just track if each position is reachable - this greedy approach works!