jump-game.ts

/**
 * 55. Jump Game  (Medium)
 * Link: https://leetcode.com/problems/jump-game/
 *
 * Each element `nums[i]` is the maximum jump length from index i. Starting at
 * index 0, return true if you can reach the last index.
 *
 * Example:
 *   Input:  nums = [2, 3, 1, 1, 4]
 *   Output: true
 *   Input:  nums = [3, 2, 1, 0, 4]
 *   Output: false        // stuck at the 0 at index 3
 *
 * Approach:
 *   Greedy from the right. Track the leftmost index from which the end is
 *   reachable (`goal`, starting at the last index). Scanning right to left, if
 *   i + nums[i] >= goal then i can reach goal, so move goal to i. If goal reaches
 *   index 0, the start can reach the end.
 *
 * Time:  O(n)
 * Space: O(1)
 */
export function canJump(nums: number[]): boolean {
  let goal = nums.length - 1;

  for (let i = nums.length - 2; i >= 0; i--) {
    if (i + nums[i] >= goal) goal = i;
  }

  return goal === 0;
}