Solution to Leetcode problem 975 Odd Even Jump

In this Leetcode problem, you are asked to find the number of indices for which, after jumping for index to index following some rules, end up in the last position of the array A.

The rules are as follow:

• For the odd numbered jumps (1st, 3rd, …), starting from i, jump to the index j such that i<j and A[i] <= A[j] and |A[j] — A[i]| is minimal among such index.
• For the even numbered jumps (2nd, 4th, …), starting from i, jump to the first index j such that i<j and A[i] >= A[j] and |A[j] — A[i]| is minimal among such index.

Frankly the definition can be quite confusing, and it is not easy to explain with words. If you have a doubt, see the oddJump() and evenJump() methods I added later.

Problem statement

One advantage to note is that the jumps are only strictly forward. Each time there is a jump, the new index j is greater than i (i<j).

We also note that there are only 2 questions to answer about each index:

• Is the index a starting index?
• If the index is reached after an odd numbers of jumps, is the even number jump from this node leading to a starting index?

To answer these questions, we only need to compute the result of an odd numbered jump from this index, as well as the result of…