975. Odd Even Jump

You are given an integer array arr. From some starting index, you can make a series of jumps. The (1st, 3rd, 5th, …) jumps in the series are called odd-numbered jumps, and the (2nd, 4th, 6th, …) jumps in the series are called even-numbered jumps. Note that the jumps are numbered, not the indices.

You may jump forward from index i to index j (with i < j) in the following way:

• During odd-numbered jumps (i.e., jumps 1, 3, 5, …), you jump to the index j such that arr[i] <= arr[j] and arr[j] is the smallest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
• During even-numbered jumps (i.e., jumps 2, 4, 6, …), you jump to the index j such that arr[i] >= arr[j] and arr[j] is the largest possible value. If there are multiple such indices j, you can only jump to the smallest such index j.
• It may be the case that for some index i, there are no legal jumps.

A starting index is good if, starting from that index, you can reach the end of the array (index arr.length - 1) by jumping some number of times (possibly 0 or more than once).

Return the number of good starting indices.

• Time : O(nlogn)
• Space : O(n)

class Solution {
    int dp[20000][2];
    int solution(vector<vector<int>>& jump, int p, bool odd) {
        if(dp[p][odd] != -1) return dp[p][odd];
        if(jump[p][odd] == -1) return dp[p][odd] = 0;
        return dp[p][odd] = solution(jump, jump[p][odd], !odd);
    }
public:
    int oddEvenJumps(vector<int>& arr) {
        vector<vector<int>> jump(arr.size(), vector<int>(2, -1));
        map<int, int> mi{{arr.back(), arr.size() - 1}}, ma{{arr.back(), arr.size() - 1}};
        for(int i = arr.size() - 2; i >= 0; i--) { //o(nlogn)
            auto minimum = mi.lower_bound(arr[i]);
            if(minimum != mi.end()) jump[i][1] = minimum->second;
            auto maximum = ma.upper_bound(arr[i]);
            if(maximum != ma.begin()) jump[i][0] = prev(maximum)->second;
            mi[arr[i]] = ma[arr[i]] = i;
        }
        memset(dp,-1,sizeof(dp));
        dp[arr.size()-1][0] = dp[arr.size()-1][1] = 1;
        int res = 0;
        
        for(int i = 0; i < arr.size(); i++) { //o(n)
            res += solution(jump, i, true);
        }
        
        return res;
    }
};