Skip to content

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<int>& A) {
    const int n = A.size();
    map<int, int> map;    // {num: min index}
    vector<bool> inc(n);  // inc[i] := can reach A[n - 1] from i w/ inc jump
    vector<bool> 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<Integer, Integer> 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<Integer, Integer> lo = map.ceilingEntry(A[i]); // min val >= A[i]
      Map.Entry<Integer, Integer> 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();
  }
}