Practice/Amazon/Leetcode 1306. Jump Game III

Leetcode 1306. Jump Game III

CodingOptional

Problem

You are given an array of non-negative integers where each element represents your maximum jump length at that position. Starting from a given index, you can move to any position by jumping exactly arr[i] steps either forward or backward from your current position i.

Your task is to determine whether it's possible to reach any index in the array that contains the value 0.

From index i, you can jump to:

• i + arr[i] (forward jump)
• i - arr[i] (backward jump)

You cannot jump outside the array boundaries. Return true if you can reach an index with value 0, otherwise return false.

Requirements

1. Implement a function that takes an array of integers and a starting index
2. Return true if any index containing value 0 is reachable from the start
3. Return false if no such index is reachable
4. Handle cycles properly (avoid infinite loops when revisiting indices)
5. All jumps must land within valid array bounds

Constraints

• 1 <= arr.length <= 5 * 10^4
• 0 <= arr[i] < arr.length
• 0 <= start < arr.length
• Your solution should run efficiently for large inputs

Examples

Example 1:

Input: arr = [4, 2, 3, 0, 3, 1, 2], start = 5 Output: true Explanation: Index 5 → Index 4 (5 - 1 = 4) Index 4 → Index 1 (4 - 3 = 1) Index 1 → Index 3 (1 + 2 = 3) Index 3 has value 0, so return true

Example 2:

Input: arr = [3, 0, 2, 1, 2], start = 2 Output: false Explanation: From index 2, we can only reach indices 0 and 4 From those positions, we cannot reach index 1 (which has value 0) We get stuck in a cycle between indices 0, 2, 3, and 4

Example 3:

Input: arr = [0, 1], start = 0 Output: true Explanation: The starting index already contains 0