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
26
27
class Solution {
 public:
  int oddEvenJumps(vector<int>& arr) {
    const int n = arr.size();
    map<int, int> map;  // {num: min index}
    // inc[i] := true if can reach arr[n - 1] from i using increasing jumps
    vector<bool> inc(n);
    // dec[i] := true if can reach arr[n - 1] from i using decreasing jumps
    vector<bool> dec(n);

    map[arr[n - 1]] = n - 1;
    inc.back() = true;
    dec.back() = true;

    for (int i = n - 2; i >= 0; --i) {
      const auto lo = map.lower_bound(arr[i]);  // the minimum value >= arr[i]
      const auto hi = map.upper_bound(arr[i]);  // the minimum value > arr[i]
      if (lo != map.cend())
        inc[i] = dec[lo->second];
      if (hi != map.cbegin())
        dec[i] = inc[prev(hi)->second];
      map[arr[i]] = i;
    }

    return ranges::count(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
25
26
27
28
class Solution {
  public int oddEvenJumps(int[] arr) {
    final int n = arr.length;
    TreeMap<Integer, Integer> map = new TreeMap<>(); // {num: min index}
    // inc[i] := true if can reach arr[n - 1] from i using increasing jumps
    int[] inc = new int[n];
    // dec[i] := true if can reach arr[n - 1] from i using increasing jumps
    int[] dec = new int[n];

    map.put(arr[n - 1], n - 1);
    inc[n - 1] = 1;
    dec[n - 1] = 1;

    for (int i = n - 2; i >= 0; --i) {
      // the minimum value >= arr[i]
      Map.Entry<Integer, Integer> lo = map.ceilingEntry(arr[i]);
      // the maximum value <= arr[i]
      Map.Entry<Integer, Integer> hi = map.floorEntry(arr[i]);
      if (lo != null)
        inc[i] = dec[(int) lo.getValue()];
      if (hi != null)
        dec[i] = inc[(int) hi.getValue()];
      map.put(arr[i], i);
    }

    return Arrays.stream(inc).sum();
  }
}