# 975. Odd Even Jump

• Time: $O(n\log n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 class Solution { public: int oddEvenJumps(vector& A) { const int n = A.size(); map map; // {num: min index} vector inc(n); // inc[i] := can reach A[n - 1] from i w/ inc jump vector dec(n); // dec[i] := can reach A[n - 1] from i w/ dec jump map[A[n - 1]] = n - 1; inc.back() = true; dec.back() = true; for (int i = n - 2; i >= 0; --i) { const auto lo = map.lower_bound(A[i]); // min val >= A[i] const auto hi = map.upper_bound(A[i]); // min val > A[i] if (lo != cend(map)) inc[i] = dec[lo->second]; if (hi != cbegin(map)) dec[i] = inc[prev(hi)->second]; map[A[i]] = i; } return count(begin(inc), end(inc), true); } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 class Solution { public int oddEvenJumps(int[] A) { final int n = A.length; TreeMap map = new TreeMap<>(); // {num: min index} int[] inc = new int[n]; // inc[i] := can reach A[n - 1] from i w/ inc jump int[] dec = new int[n]; // dec[i] := can reach A[n - 1] from i w/ dec jump map.put(A[n - 1], n - 1); inc[n - 1] = 1; dec[n - 1] = 1; for (int i = n - 2; i >= 0; --i) { Map.Entry lo = map.ceilingEntry(A[i]); // min val >= A[i] Map.Entry hi = map.floorEntry(A[i]); // max val <= A[i] if (lo != null) inc[i] = dec[(int) lo.getValue()]; if (hi != null) dec[i] = inc[(int) hi.getValue()]; map.put(A[i], i); } return Arrays.stream(inc).sum(); } }