Pointer DP

Ugly Number II

nth number where it only has prime factor 2, 3 or 5.

You can obviously bfs via a set or pq. The dp pointer way has no log factor. Idea it to just keep 3 pointers as to what to multiply by 2, 3 or 5 and building on the fly as needed since you always know where the next smallest can be possible from via the ptrs.

Odd Even Jump

Link: https://leetcode.com/problems/odd-even-jump/

As a trick, you can sort the elemnts with their indices to find the next greater index using mono stack but since you are soring anyway, easier to use map.

int oddEvenJumps(vector<int>& arr) {
    // rephrase:
    // i do two types of jumps, starting with odd type
    // in odd type, in the suffix ahead, choose the min element >= cur ( not necessarily nearest )
    // in even type, in the suffix ahead, choose the max element <= cur
 
    // (node, even or odd of the next jump type) makes the state unique
    // can iterate in reverse
 
    int n = arr.size();
    map<int, int> mp;
    mp[arr.back()] = n - 1;
    vector<vector<int>> dp(n, vector<int>(2));
    dp.back()[0] = dp.back()[1] = 1;  // last is good always
 
    int ans = 1;
    for (int i = n - 2; i >= 0; i--) {
        int odd_jump = -1, even_jump = -1;
        int cur = arr[i];
        auto less_eq = mp.upper_bound(cur);
        if (less_eq != mp.begin())
            even_jump = prev(less_eq)->second;
        auto gt_eq = mp.lower_bound(cur);
        if (gt_eq != mp.end())
            odd_jump = gt_eq->second;
 
        // jump type is odd ( 0 )
        if (odd_jump != -1) {
            dp[i][0] |= dp[odd_jump][1];
        }
        if (even_jump != -1) {
            dp[i][1] |= dp[even_jump][0];
        }
        ans += dp[i][0];
        mp[cur] = i;  // for the same value you overwrite so among equal values, this will be the closest
    }
    return ans;
}