Practice/Amazon/Leetcode 55. Jump Game

Leetcode 55. Jump Game

CodingOptional

Problem

You are given an array of non-negative integers representing a series of platforms. Each element in the array indicates the maximum number of positions you can jump forward from that platform.

Starting at the first platform (index 0), determine whether it is possible to reach the final platform (the last index in the array).

Requirements

1. Return true if you can reach the last index, false otherwise
2. You may jump any number of positions from 1 up to the value at your current position
3. You must use an efficient algorithm that avoids checking every possible path

Constraints

• 1 ≤ platforms.length ≤ 104
• 0 ≤ platforms[i] ≤ 105
• Time complexity should be O(n) where n is the length of the array
• Space complexity should be O(1)

Examples

Example 1:

Input: platforms = [2, 3, 1, 1, 4] Output: true Explanation: Jump 1 step from index 0 to index 1, then jump 3 steps to the last index (index 4).

Example 2:

Input: platforms = [3, 2, 1, 0, 4] Output: false Explanation: No matter which path you take, you will eventually land on index 3. Since the value there is 0, you cannot make any further jumps and cannot reach the final index.

Example 3:

Input: platforms = [0] Output: true Explanation: You are already at the last index, so no jump is required.