Leetcode Problem 975. Odd Even Jump

975. Odd Even Jump

Leetcode Solutions

Dynamic Programming with Monotonic Stack

  1. Initialize two boolean arrays odd and even to keep track of whether an index can reach the end with an odd or even jump respectively.
  2. Initialize the last index of both odd and even arrays to True since the last index can always reach the end.
  3. Sort the indices of the array based on their values in ascending order for odd jumps and in descending order for even jumps.
  4. Use a monotonic stack to find the next greater index for odd jumps and the next smaller index for even jumps.
  5. Iterate over the array from the second last index to the first index: a. For odd jumps, if there is a next greater index, set odd[i] to even[next_greater_index]. b. For even jumps, if there is a next smaller index, set even[i] to odd[next_smaller_index].
  6. Count the number of True values in the odd array, which represents the number of good starting indices.
UML Thumbnail

Dynamic Programming with Binary Search

Ask Question

Programming Language
image/screenshot of info(optional)
Full Screen
Loading...

Suggested Answer

Answer
Full Screen
Copy Answer Code
Loading...