Odd Even Jump

hard array dp stack monotonic stack

Problem

Starting from any index, odd-numbered jumps go to the next index with the smallest value ≥ current; even-numbered jumps go to the next index with the largest value ≤ current. Count start positions that reach the last index.

Inputarr = [10,13,12,14,15]

Output2

Precompute oddNext and evenNext via sorted-index stacks; back-fill DP.

arr (comma-separated)

def oddEvenJumps(arr):
    n = len(arr)
    def next_arr(idx):
        st = []
        result = [-1] * n
        for i in idx:
            while st and i > st[-1]:
                result[st.pop()] = i
            st.append(i)
        return result
    a = sorted(range(n), key=lambda i: (arr[i], i))
    odd_next = next_arr(a)
    b = sorted(range(n), key=lambda i: (-arr[i], i))
    even_next = next_arr(b)
    odd = [False]*n; even = [False]*n
    odd[-1] = even[-1] = True
    for i in range(n - 2, -1, -1):
        if odd_next[i] != -1: odd[i] = even[odd_next[i]]
        if even_next[i] != -1: even[i] = odd[even_next[i]]
    return sum(odd)

function oddEvenJumps(arr) {
  const n = arr.length;
  function nextArr(idx) {
    const st = []; const res = new Array(n).fill(-1);
    for (const i of idx) {
      while (st.length && i > st[st.length - 1]) res[st.pop()] = i;
      st.push(i);
    }
    return res;
  }
  const a = [...Array(n).keys()].sort((x, y) => arr[x] === arr[y] ? x - y : arr[x] - arr[y]);
  const oddN = nextArr(a);
  const b = [...Array(n).keys()].sort((x, y) => arr[x] === arr[y] ? x - y : arr[y] - arr[x]);
  const evenN = nextArr(b);
  const odd = new Array(n).fill(false), even = new Array(n).fill(false);
  odd[n - 1] = even[n - 1] = true;
  for (let i = n - 2; i >= 0; i--) {
    if (oddN[i] !== -1) odd[i] = even[oddN[i]];
    if (evenN[i] !== -1) even[i] = odd[evenN[i]];
  }
  return odd.filter(Boolean).length;
}

class Solution {
    public int oddEvenJumps(int[] arr) {
        int n = arr.length;
        Integer[] aIdx = new Integer[n], bIdx = new Integer[n];
        for (int i = 0; i < n; i++) { aIdx[i] = i; bIdx[i] = i; }
        Arrays.sort(aIdx, (x, y) -> arr[x] == arr[y] ? x - y : arr[x] - arr[y]);
        Arrays.sort(bIdx, (x, y) -> arr[x] == arr[y] ? x - y : arr[y] - arr[x]);
        int[] oddN = nextArr(aIdx, n), evenN = nextArr(bIdx, n);
        boolean[] odd = new boolean[n], even = new boolean[n];
        odd[n - 1] = even[n - 1] = true;
        int count = 1;
        for (int i = n - 2; i >= 0; i--) {
            if (oddN[i] != -1) odd[i] = even[oddN[i]];
            if (evenN[i] != -1) even[i] = odd[evenN[i]];
            if (odd[i]) count++;
        }
        return count;
    }
    int[] nextArr(Integer[] idx, int n) {
        int[] res = new int[n]; Arrays.fill(res, -1);
        Deque<Integer> st = new ArrayDeque<>();
        for (int i : idx) {
            while (!st.isEmpty() && i > st.peek()) res[st.pop()] = i;
            st.push(i);
        }
        return res;
    }
}

int oddEvenJumps(vector<int>& arr) {
    int n = (int)arr.size();
    auto nextArr = [&](vector<int>& idx) {
        vector<int> res(n, -1); stack<int> st;
        for (int i : idx) {
            while (!st.empty() && i > st.top()) { res[st.top()] = i; st.pop(); }
            st.push(i);
        }
        return res;
    };
    vector<int> aIdx(n), bIdx(n);
    iota(aIdx.begin(), aIdx.end(), 0); iota(bIdx.begin(), bIdx.end(), 0);
    sort(aIdx.begin(), aIdx.end(), [&](int x, int y){ return arr[x] == arr[y] ? x < y : arr[x] < arr[y]; });
    sort(bIdx.begin(), bIdx.end(), [&](int x, int y){ return arr[x] == arr[y] ? x < y : arr[x] > arr[y]; });
    auto oddN = nextArr(aIdx), evenN = nextArr(bIdx);
    vector<bool> odd(n, false), even(n, false);
    odd[n - 1] = even[n - 1] = true; int count = 1;
    for (int i = n - 2; i >= 0; i--) {
        if (oddN[i] != -1) odd[i] = even[oddN[i]];
        if (evenN[i] != -1) even[i] = odd[evenN[i]];
        if (odd[i]) count++;
    }
    return count;
}

Explanation

From any start you alternate odd jumps (to the nearest later index with the smallest value >= current) and even jumps (to the nearest later index with the largest value <= current), and we count the starts that can reach the last index. The key insight is that whether a start succeeds depends only on where its jumps land, so we precompute every jump target and then fill the answer backward.

To find each odd jump target we sort the indices by value (ties broken by index) and run a monotonic stack that resolves each index to its "next greater-or-equal" neighbor. Sorting by value descending and running the same stack gives the even targets. This is the oddNext / evenNext arrays.

Now we DP from the end. The last index trivially reaches itself, so odd[last] = even[last] = true. Walking backward, odd[i] is true if taking its odd jump leads to an index that is true on its even turn (even[oddNext[i]]), and symmetrically even[i] follows odd[evenNext[i]] — because the parity flips after each jump.

The answer is the number of indices where odd[i] is true, since every journey starts with an odd jump.

Example: arr = [10,13,12,14,15] yields 2 good starting positions. Sorting plus the linear stack and back-fill make this O(n log n).

Time: O(n log n) Space: O(n)