LC make an array to be strictly increasing

lc_makeincr.md

Given 2 arrays, find if it is possible to make the first to be strictly increasing by replace some of it's elements with those from array2. Solution using memoization and dfs. It got TLE, I guess due to memory allocation because if I use static it worked, whatever.

LC

class Solution {
public:
    vector<vector<int>> mem;
    
    // The main thing is to define the state:
    //      <position in a, position in b, value of the last>
    // Position b is to define the next possible position in array b, so it
    // is not required to take exactly b[j] element but rather find an element
    // greater than prev in b starting from j -- this is just an optimization 
    // and formally is not part of the state.
    //
    // State is a vertex in a graph. Each vertex might have up to 2 children:
    // one if we replace the current a[i] element to any b[j] st b[j] > prev
    // another one if we do not replace, must be a[i] > prev
    int dfs(vector<int>& a, vector<int>& b, int i, int j, int prev) {
        if (i >= a.size()) {
            mem[i][j] = 0; // success
            return mem[i][j];
        }
        
        int jnext = upper_bound(b.begin() + j, b.end(), prev) - b.begin();
        if (mem[i][jnext] < 1e9) 
            return mem[i][jnext];
        
        int resFromLeftChild = 1e9;
        if (jnext < b.size()) //else it is impossible to replace
            resFromLeftChild = dfs(a, b, i+1, jnext, b[jnext]) + 1; 
        
        int resFromRightChild = 1e9;
        if (a[i] > prev)
            resFromRightChild = dfs(a, b, i+1, jnext, a[i]) ;
        
        mem[i][jnext] = min(resFromLeftChild, resFromRightChild);
        return mem[i][jnext];
    }
    
    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        mem.resize(arr1.size() + 1, vector<int>(arr2.size() + 1, 1e9));
        // to be able to search log N in arr2
        sort(arr2.begin(), arr2.end());
        // remove dublicates
        arr2.resize(unique(arr2.begin(), arr2.end()) - arr2.begin());
        
        int res = dfs(arr1, arr2, 0, 0, -1e9);
        if (res > arr2.size()) return -1;
        return res;
    }
};