<p>Given two integer arrays&nbsp;<code>arr1</code> and <code>arr2</code>, return the minimum number of operations (possibly zero) needed&nbsp;to make <code>arr1</code> strictly increasing.</p>

<p>In one operation, you can choose two indices&nbsp;<code>0 &lt;=&nbsp;i &lt; arr1.length</code>&nbsp;and&nbsp;<code>0 &lt;= j &lt; arr2.length</code>&nbsp;and do the assignment&nbsp;<code>arr1[i] = arr2[j]</code>.</p>

<p>If there is no way to make&nbsp;<code>arr1</code>&nbsp;strictly increasing,&nbsp;return&nbsp;<code>-1</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
<strong>Output:</strong> 1
<strong>Explanation:</strong> Replace <code>5</code> with <code>2</code>, then <code>arr1 = [1, 2, 3, 6, 7]</code>.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> arr1 = [1,5,3,6,7], arr2 = [4,3,1]
<strong>Output:</strong> 2
<strong>Explanation:</strong> Replace <code>5</code> with <code>3</code> and then replace <code>3</code> with <code>4</code>. <code>arr1 = [1, 3, 4, 6, 7]</code>.
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
<strong>Output:</strong> -1
<strong>Explanation:</strong> You can&#39;t make <code>arr1</code> strictly increasing.</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= arr1.length, arr2.length &lt;= 2000</code></li>
	<li><code>0 &lt;= arr1[i], arr2[i] &lt;= 10^9</code></li>
</ul>

<p>&nbsp;</p>

class Solution {
public:
    struct pair_hash {
        std::size_t operator()(const std::pair<int, int>& p) const {
            // Combine the hashes of the two integers
            return std::hash<int>{}(p.first) ^
                   (std::hash<int>{}(p.second) << 1);
        }
    };

    int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
        std::sort(arr2.begin(), arr2.end());
        int result = 0;
        std::unordered_map<std::pair<int, int>, int, pair_hash> memory;
        bool success = Dfs(arr1, arr2, 0, -1, &result, memory);
        if (success)
            return result;
        return -1;
    }

    bool Dfs(const vector<int>& arr1, const std::vector<int>& arr2, int i,
             int prev_value, int* result,
             std::unordered_map<std::pair<int, int>, int, pair_hash>& memory) {
        auto key = std::make_pair(i, prev_value);
        if (memory.contains(key)) {
            const int m = memory[key];
            if (m >= 0) {
                *result = m;
                return true;
            }
            return false;
        }
        if (i == arr1.size()) {
            *result = 0;
            return true;
        }
        const int replacement = FindSmallestGreaterThan(arr2, prev_value);
        const int curr_value = arr1[i];
        if (curr_value <= prev_value) {
            if (replacement == -1)
                return false;
            bool success = Dfs(arr1, arr2, i + 1, replacement, result, memory);
            if (!success) {
                memory[key] = -1;
                return false;
            }
            *result += 1;
            memory[key] = *result;
            return true;
        } else {
            bool success = Dfs(arr1, arr2, i + 1, curr_value, result, memory);
            bool alternative_success = false;
            int alternative_result = 0;
            if (replacement >= 0 && replacement < curr_value) {
                alternative_success =
                    Dfs(arr1, arr2, i + 1, replacement, &alternative_result, memory);
                alternative_result += 1;
            }
            if (success && alternative_success) {
                *result = std::min(*result, alternative_result);
                memory[key] = *result;
                return true;
            }
            if (alternative_success) {
                *result = alternative_result;
            }
            bool valid = success || alternative_success;
            if (valid) {
                memory[key] = *result;
            } else {
                memory[key] = -1;
            }
            return valid;
        }
    }

    /* Returns -1 if none is found. */
    int FindSmallestGreaterThan(const std::vector<int>& arr2, int i) {
        auto it = std::upper_bound(arr2.begin(), arr2.end(), i);
        if (it == arr2.end())
            return -1;
        return *it;
    }
};
92616