LeetCode 975: Odd Even Jump Solution

Master LeetCode problem 975 (Odd Even Jump), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

975. Odd Even Jump

Hard

Array Dynamic Programming Stack Monotonic Stack Ordered Set

Problem Explanation

Explanation:

To solve this problem, we can use a stack and dynamic programming. We will create two arrays, odd and even, to store the next jump indices for odd and even jumps respectively. We will iterate the array from right to left and use a TreeMap to store the indices of elements that have been visited so far.

We start by initializing odd and even arrays with the same size as the input array, filled with -1.
We create a TreeMap to store the indices of elements we have visited so far.
We iterate the array from right to left. For each element, we find the next jump index for both odd and even jumps:
- For odd jumps, we find the smallest value that is greater than or equal to the current element using the TreeMap.
- For even jumps, we find the largest value that is less than or equal to the current element using the TreeMap.
We update the odd and even arrays with the next jump indices.
We create two boolean arrays, canReachEndOdd and canReachEndEven, to store whether we can reach the end from each index for odd and even jumps.
We iterate the array from left to right and update the canReachEndOdd and canReachEndEven arrays based on the next jump indices found earlier.
We count the number of starting indices where we can reach the end by following the odd jumps.

Solution Code

import java.util.*;

class Solution {
    public int oddEvenJumps(int[] arr) {
        int n = arr.length;
        boolean[] canReachEndOdd = new boolean[n];
        boolean[] canReachEndEven = new boolean[n];
        canReachEndOdd[n - 1] = canReachEndEven[n - 1] = true;

        TreeMap<Integer, Integer> map = new TreeMap<>();
        map.put(arr[n - 1], n - 1);

        int[] odd = new int[n];
        int[] even = new int[n];
        Arrays.fill(odd, -1);
        Arrays.fill(even, -1);

        int result = 1;

        for (int i = n - 2; i >= 0; i--) {
            Map.Entry<Integer, Integer> oddEntry = map.ceilingEntry(arr[i]);
            Map.Entry<Integer, Integer> evenEntry = map.floorEntry(arr[i]);

            if (oddEntry != null) {
                odd[i] = oddEntry.getValue();
                canReachEndOdd[i] = canReachEndEven[oddEntry.getValue()];
            }

            if (evenEntry != null) {
                even[i] = evenEntry.getValue();
                canReachEndEven[i] = canReachEndOdd[evenEntry.getValue()];
            }

            map.put(arr[i], i);

            if (canReachEndOdd[i]) {
                result++;
            }
        }

        return result;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 975 (Odd Even Jump)?

This page provides optimized solutions for LeetCode problem 975 (Odd Even Jump) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 975 (Odd Even Jump)?

The time complexity for LeetCode 975 (Odd Even Jump) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 975 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 975 in Java, C++, or Python.

Back to LeetCode Solutions