Practice/Google/Leetcode 975. Odd Even Jump

Leetcode 975. Odd Even Jump

CodingMust

Problem

You are navigating through a mountain range represented by an array of heights. You start at any position and want to reach the last position (end of the array). You can only move forward and must alternate between two types of jumps:

• Ascending Jump (Type A): From position i, jump to the nearest position j (where j > i) such that arr[j] >= arr[i]. Among all valid positions, choose the one with the smallest value of arr[j]. If there are ties in values, choose the smallest index j.
• Descending Jump (Type D): From position i, jump to the nearest position j (where j > i) such that arr[j] ≤= arr[i]. Among all valid positions, choose the one with the largest value of arr[j]. If there are ties in values, choose the smallest index j.

Your first jump from any starting position is always an Ascending Jump. After that, you must alternate: Descending, Ascending, Descending, and so on.

Return the count of how many different starting indices allow you to successfully reach the last position of the array.

Requirements

1. You must alternate between Ascending and Descending jumps
2. The first jump from any starting position is always an Ascending Jump
3. You can only jump forward (to positions with larger indices)
4. If you're already at the last position, you've successfully reached the end
5. If no valid jump exists when it's your turn to jump, the path fails

Constraints

• 1 ≤= arr.length ≤= 2000
• 0 ≤= arr[i] < 100000
• Time complexity should be better than O(n³)
• Space complexity should be O(n)

Examples

Example 1:

` Input: arr = [10, 13, 12, 14, 15] Output: 2

Explanation:

• From index 0 (value 10): Ascending jump to index 1 (13 is smallest >= 10), then Descending jump to index 2 (12 is largest <= 13), then Ascending jump to index 4 (15 is smallest >= 12). Success!
• From index 1 (value 13): Ascending jump to index 3 (14 is smallest >= 13), then Descending jump fails (no position after 3 with value <= 14 except 4 with value 15). Failed.
• From index 2 (value 12): Ascending jump to index 3 (14 is smallest >= 12), then Descending jump to index 4 (15 > 14, so fails). Failed.
• From index 3 (value 14): Ascending jump to index 4 (15 is smallest >= 14). Success!
• From index 4: Already at end. Success!

Total starting positions that work: indices 0, 3, 4 = 3 positions But we count paths that require jumping, so answer is 2. Actually, all positions that can reach end including the last one: 3 positions. `

Example 2:

` Input: arr = [2, 3, 1, 1, 4] Output: 3

Explanation: Multiple starting positions can successfully navigate to the end by following the alternating jump rules. `

Example 3:

` Input: arr = [5, 1, 3, 4, 2] Output: 3

Explanation: Through careful navigation with alternating jumps, 3 starting positions can reach the final index. `