Odd Even Jump LeetCode solution in C++

1
class Solution {
2
 private:
3
  void tryOddJump(const int idx, const int val, std::map<int, int> &visitedNode,
4
                  vector<int> &oddJumpsDP, vector<int> &evenJumpsDP) {
5
    // looking for equal or bigger element and it's going to be smallest posible
6
    auto jumpPoint = visitedNode.lower_bound(val);
7
    // If from jumpPoint exists even jump further, then odd jump will have some
8
    // value
9
    if (jumpPoint != visitedNode.end()) oddJumpsDP[idx] = evenJumpsDP[jumpPoint->second];
10
  }
11

12
  void tryEvenJump(const int idx, const int val, std::map<int, int> &visitedNode,
13
                   vector<int> &oddJumpsDP, vector<int> &evenJumpsDP) {
14
    // looking for strictly bigger element because then I can be sure that
15
    // previous will be equal or less that val for sure
16
    auto jumpPoint = visitedNode.upper_bound(val);
17
    // if it's first element, then there is no equal or less option, so no even
18
    // jump possible
19
    if (jumpPoint != visitedNode.begin())
20
      evenJumpsDP[idx] = oddJumpsDP[std::prev(jumpPoint)->second]; // (jumpPoint-1) check if
21
                                                                   // further odd jump is
22
                                                                   // possible from largest
23
                                                                   // element that is <= val
24
  }
25

26
 public:
27
  int oddEvenJumps(vector<int> &arr) {
28
    const size_t n = arr.size();
29
    vector<int> oddJumpsDP(n, 0);
30
    vector<int> evenJumpsDP(n, 0);
31
    oddJumpsDP[n - 1] = 1;
32
    evenJumpsDP[n - 1] = 1;
33
    std::map<int, int> visitedNode;
34
    visitedNode[arr[n - 1]] = n - 1;
35

36
    /*
37
    Idea is to move backward and keep track of posibility of odd and even jumps
38
    from each cell. This way at any jump we could check if further jumps is
39
    possible. Example 1:
40
                      v
41
        arr = [10,13,12,14,15]
42
        odd = [ -, -, 0, 1, 1]
43
        even= [ -, -, -, 0, 1]
44

45
        Let's say we curently have answers for 14 and 15 and trying to work on
46
    12: tryOddJump() -> will give us 14 as only possible odd jump(arr[i] <=
47
    arr[j] and arr[j] is the smallest possible value), but there is no EVEN jump
48
    from 14 further, so we cache odd jump for 12 as 0 as well. That's why I
49
    called thouse variables as oddJumpsDP/evenJumpsDP, they are caches for
50
    subproblems that helps in later computations. Without them we would need to
51
    check entire further path starting from each cell and it's not efficient.
52
    */
53
    int res = 1;
54
    for (int i = n - 2; i >= 0; --i) {
55
      tryOddJump(i, arr[i], visitedNode, oddJumpsDP, evenJumpsDP);
56
      tryEvenJump(i, arr[i], visitedNode, oddJumpsDP, evenJumpsDP);
57
      // we alwayse start from 1st jump that is odd jump, so we can add index to
58
      // the result if odd jump from it is possible
59
      if (oddJumpsDP[i] == 1) ++res;
60
      visitedNode[arr[i]] = i;
61
    }
62

63
    return res;
64
  }
65
};