Code Implementation

from bisect import bisect_left, bisect_right
def oddEvenJumps(arr):
    n = len(arr)
    odd = [False] * n
    even = [False] * n
    odd[-1] = even[-1] = True

    # Pair value with index and sort for odd jumps (smallest >= arr[i])
    idxs = sorted(range(n), key=lambda i: (arr[i], i))
    next_higher = [None] * n
    stack = []
    for i in idxs:
        while stack and i > stack[-1]:
            next_higher[stack.pop()] = i
        stack.append(i)

    # Pair value with index and sort for even jumps (largest <= arr[i])
    idxs = sorted(range(n), key=lambda i: (-arr[i], i))
    next_lower = [None] * n
    stack = []
    for i in idxs:
        while stack and i > stack[-1]:
            next_lower[stack.pop()] = i
        stack.append(i)

    for i in range(n - 2, -1, -1):
        if next_higher[i] is not None:
            odd[i] = even[next_higher[i]]
        if next_lower[i] is not None:
            even[i] = odd[next_lower[i]]

    return sum(odd)
      

#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

class Solution {
public:
    int oddEvenJumps(vector<int>& arr) {
        int n = arr.size();
        vector<bool> odd(n, false), even(n, false);
        odd[n-1] = even[n-1] = true;
        vector<int> next_higher(n, -1), next_lower(n, -1);

        // Next higher
        vector<int> idxs(n);
        for (int i = 0; i < n; ++i) idxs[i] = i;
        sort(idxs.begin(), idxs.end(), [&arr](int i, int j) {
            return arr[i] == arr[j] ? i < j : arr[i] < arr[j];
        });
        stack<int> st;
        for (int i : idxs) {
            while (!st.empty() && i > st.top()) {
                next_higher[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }

        // Next lower
        sort(idxs.begin(), idxs.end(), [&arr](int i, int j) {
            return arr[i] == arr[j] ? i < j : arr[i] > arr[j];
        });
        while (!st.empty()) st.pop();
        for (int i : idxs) {
            while (!st.empty() && i > st.top()) {
                next_lower[st.top()] = i;
                st.pop();
            }
            st.push(i);
        }

        for (int i = n-2; i >= 0; --i) {
            if (next_higher[i] != -1)
                odd[i] = even[next_higher[i]];
            if (next_lower[i] != -1)
                even[i] = odd[next_lower[i]];
        }
        int res = 0;
        for (bool b : odd) if (b) ++res;
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int oddEvenJumps(int[] arr) {
        int n = arr.length;
        boolean[] odd = new boolean[n];
        boolean[] even = new boolean[n];
        odd[n-1] = even[n-1] = true;
        int[] nextHigher = new int[n];
        int[] nextLower = new int[n];

        Integer[] idxs = new Integer[n];
        for (int i = 0; i < n; i++) idxs[i] = i;
        Arrays.sort(idxs, (a, b) -> arr[a] != arr[b] ? Integer.compare(arr[a], arr[b]) : Integer.compare(a, b));
        Stack<Integer> stack = new Stack<>();
        Arrays.fill(nextHigher, -1);
        for (int i : idxs) {
            while (!stack.isEmpty() && i > stack.peek()) {
                nextHigher[stack.pop()] = i;
            }
            stack.push(i);
        }

        Arrays.sort(idxs, (a, b) -> arr[a] != arr[b] ? Integer.compare(arr[b], arr[a]) : Integer.compare(a, b));
        Arrays.fill(nextLower, -1);
        stack.clear();
        for (int i : idxs) {
            while (!stack.isEmpty() && i > stack.peek()) {
                nextLower[stack.pop()] = i;
            }
            stack.push(i);
        }

        for (int i = n - 2; i >= 0; i--) {
            if (nextHigher[i] != -1)
                odd[i] = even[nextHigher[i]];
            if (nextLower[i] != -1)
                even[i] = odd[nextLower[i]];
        }

        int res = 0;
        for (boolean b : odd) if (b) res++;
        return res;
    }
}
      

var oddEvenJumps = function(arr) {
    const n = arr.length;
    const odd = new Array(n).fill(false);
    const even = new Array(n).fill(false);
    odd[n-1] = even[n-1] = true;

    function makeNext(sortedIdxs) {
        const res = new Array(n).fill(null);
        const stack = [];
        for (let i of sortedIdxs) {
            while (stack.length && i > stack[stack.length-1]) {
                res[stack.pop()] = i;
            }
            stack.push(i);
        }
        return res;
    }

    // For odd jumps: sort by value asc, then index asc
    let idxs = Array.from({length: n}, (_, i) => i);
    idxs.sort((a, b) => arr[a] - arr[b] || a - b);
    const nextHigher = makeNext(idxs);

    // For even jumps: sort by value desc, then index asc
    idxs.sort((a, b) => arr[b] - arr[a] || a - b);
    const nextLower = makeNext(idxs);

    for (let i = n-2; i >= 0; --i) {
        if (nextHigher[i] !== null) odd[i] = even[nextHigher[i]];
        if (nextLower[i] !== null) even[i] = odd[nextLower[i]];
    }
    return odd.filter(Boolean).length;
};
      

Problem Description

You are given an integer array arr of length n. Starting from any index i, you can make a sequence of jumps to other indices according to the following rules:

• On the odd-numbered jump (first, third, etc.), you jump to the smallest index j such that j > i and arr[j] >= arr[i] and arr[j] is as small as possible. If there are multiple such indices, choose the smallest j.
• On the even-numbered jump (second, fourth, etc.), you jump to the smallest index j such that j > i and arr[j] <= arr[i] and arr[j] is as large as possible. If there are multiple such indices, choose the smallest j.
• If there is no valid j, you stop jumping from that index.

An index is called "good" if starting from it, you can reach the end of the array (index n-1) by making a sequence of jumps following the rules above.

Your task: Return the total number of "good" starting indices in arr.

Constraints:

• 1 <= arr.length <= 2 * 10⁴
• 0 <= arr[i] < 10⁵
• There is always at least one solution (the last index is always "good").

Thought Process

The problem asks for the number of starting indices from which you can reach the end of the array by alternating between "odd" and "even" jumps, each with their own rules. At first glance, this seems to require simulating all possible jump sequences from each index, which could be very slow for large arrays.

A brute-force approach would be to, for each starting index, simulate all jumps until you either reach the end or get stuck. However, this would result in a time complexity of O(n²) or worse, which is not feasible for large inputs.

To optimize, we need to precompute, for each index, where the next "odd" and "even" jump would land. Once we have this information, we can use dynamic programming to determine if a given index can reach the end via valid jumps, by working backwards from the end of the array.

The key insight is that the "next jump" for each index depends only on the array structure, and we can use sorting and a stack to efficiently compute these next jumps for all indices.

Solution Approach

Let's break down the solution step by step:

1. Precompute Next Jumps:
   • For each index i, find the next index j you would jump to on an odd jump (smallest j > i with arr[j] >= arr[i], and arr[j] is as small as possible).
   • Similarly, for each index i, find the next index j for an even jump (smallest j > i with arr[j] <= arr[i], and arr[j] is as large as possible).
   • To do this efficiently, sort indices by arr[i] (ascending for odd, descending for even) and use a stack to process indices in order, assigning "next jump" pointers.
2. Dynamic Programming:
   • Create two boolean arrays, odd and even, where odd[i] is true if you can reach the end from i using an odd jump first, and even[i] is true if you can reach the end from i using an even jump first.
   • The base case: the last index is always "good" for both odd and even jumps.
   • Iterate backwards through the array, filling in odd and even using the precomputed next jumps:
     • If the next odd jump from i is j, then odd[i] = even[j].
     • If the next even jump from i is j, then even[i] = odd[j].
3. Count Good Indices:
   • Return the number of indices where odd[i] is true, since we always start with an odd jump.

The use of sorting and stacks allows us to precompute the next jumps efficiently, and the dynamic programming step ensures we only process each index once.

Example Walkthrough

Let's walk through an example with arr = [10, 13, 12, 14, 15]:

1. Precompute Next Jumps:
   • For index 0 (10): next odd jump is index 1 (13), because 13 is the smallest value ≥ 10 to the right.
   • For index 1 (13): next odd jump is index 2 (12), but 12 is not ≥ 13, so look for ≥ 13, which is index 3 (14).
   • For index 2 (12): next odd jump is index 3 (14).
   • For index 3 (14): next odd jump is index 4 (15).
   • For index 4 (15): no jump possible.
   • Even jumps are similar, but look for ≤ current value and as large as possible.
2. Dynamic Programming Step:
   • The last index (4) is always "good": odd[4] = even[4] = True.
   • For index 3: odd jump to 4, so odd[3] = even[4] = True; even jump (no valid index), so even[3] = False.
   • For index 2: odd jump to 3, so odd[2] = even[3] = False; even jump to 3, so even[2] = odd[3] = True.
   • For index 1: odd jump to 3, so odd[1] = even[3] = False; even jump to 2, so even[1] = odd[2] = False.
   • For index 0: odd jump to 1, so odd[0] = even[1] = False; even jump (no valid index), so even[0] = False.
3. Count Good Indices:
   • Indices with odd[i] = True are 3 and 4. So the answer is 2.

This process efficiently computes which indices are "good" by working backwards and using precomputed jump targets.

Time and Space Complexity

• Brute-force Approach:
  • For each index, simulating all possible jumps can take up to O(n) time per index, resulting in O(n²) total time.
  • This is not feasible for large arrays.
• Optimized Approach:
  • Precomputing the next jumps uses sorting and a stack, which takes O(n log n) time for each of odd and even jumps.
  • The dynamic programming step is O(n), as we process each index once.
  • Overall time complexity: O(n log n).
  • Space complexity: O(n) for the jump arrays and the DP arrays.

Summary

The Odd Even Jump problem challenges us to find efficient ways to simulate a sequence of jumps through an array under alternating rules. By precomputing the next valid jumps using sorting and stacks, and leveraging dynamic programming to propagate reachability from the end of the array backwards, we achieve an efficient O(n log n) solution. The approach is elegant because it decouples the jump-finding logic from the reachability logic, and uses well-known algorithms (sorting, stack-based processing, and DP) in a creative way to solve a complex problem.