Practice/Google/Leetcode 403. Frog Jump

Leetcode 403. Frog Jump

CodingMust

Problem

A frog is trying to cross a river by jumping on stones. The stones are positioned at various distances along the river, represented by an array of integers where each value indicates the position of a stone from the starting bank.

The frog begins on the first stone (position 0) and wants to reach the last stone. On the first jump, the frog can only jump exactly 1 unit forward. After that, if the frog's last jump was k units, then its next jump must be either k - 1, k, or k + 1 units. The frog can only land on stones, not in the water.

Given a sorted array of stone positions, determine whether the frog can successfully cross the river and reach the last stone.

Requirements

1. Return true if the frog can reach the last stone, false otherwise
2. The frog must land exactly on stone positions (no partial landings)
3. The first jump must be exactly 1 unit
4. Each subsequent jump must be within 1 unit of the previous jump distance
5. Handle cases where no valid path exists

Constraints

• 2 ≤ stones.length ≤ 2000
• 0 ≤ stones[i] ≤ 2³¹ - 1
• stones[0] is always 0
• stones is sorted in strictly ascending order

Examples

Example 1:

Input: stones = [0, 1, 3, 5, 6, 8, 12, 17] Output: true Explanation: Jump sequence: 0→1 (k=1), 1→3 (k=2), 3→5 (k=2), 5→8 (k=3), 8→12 (k=4), 12→17 (k=5)

Example 2:

Input: stones = [0, 1, 2, 3, 4, 8, 9, 11] Output: false Explanation: The frog can reach stone at position 4, but cannot make a jump large enough to reach position 8. From position 4, the frog's last jump was 1, so it can only jump 0, 1, or 2 units forward. This would land at positions 4, 5, or 6, none of which have stones.

Example 3:

Input: stones = [0, 1] Output: true Explanation: The frog makes one jump of 1 unit from position 0 to position 1.