<p>You are given two integer arrays of the same length <code>nums1</code> and <code>nums2</code>. In one operation, you are allowed to swap <code>nums1[i]</code> with <code>nums2[i]</code>.</p>

<ul>
	<li>For example, if <code>nums1 = [1,2,3,<u>8</u>]</code>, and <code>nums2 = [5,6,7,<u>4</u>]</code>, you can swap the element at <code>i = 3</code> to obtain <code>nums1 = [1,2,3,4]</code> and <code>nums2 = [5,6,7,8]</code>.</li>
</ul>

<p>Return <em>the minimum number of needed operations to make </em><code>nums1</code><em> and </em><code>nums2</code><em> <strong>strictly increasing</strong></em>. The test cases are generated so that the given input always makes it possible.</p>

<p>An array <code>arr</code> is <strong>strictly increasing</strong> if and only if <code>arr[0] &lt; arr[1] &lt; arr[2] &lt; ... &lt; arr[arr.length - 1]</code>.</p>

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

<pre>
<strong>Input:</strong> nums1 = [1,3,5,4], nums2 = [1,2,3,7]
<strong>Output:</strong> 1
<strong>Explanation:</strong> 
Swap nums1[3] and nums2[3]. Then the sequences are:
nums1 = [1, 3, 5, 7] and nums2 = [1, 2, 3, 4]
which are both strictly increasing.
</pre>

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

<pre>
<strong>Input:</strong> nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9]
<strong>Output:</strong> 1
</pre>

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

<ul>
	<li><code>2 &lt;= nums1.length &lt;= 10<sup>5</sup></code></li>
	<li><code>nums2.length == nums1.length</code></li>
	<li><code>0 &lt;= nums1[i], nums2[i] &lt;= 2 * 10<sup>5</sup></code></li>
</ul>

const int ZERO = []() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    int solverec(vector<int>& n1, vector<int>& n2, int index, bool swapped)
    {
        if(index >= n1.size())
        return 0;

        int prev1 = n1[index-1];
        int prev2 = n2[index-1];

        if(swapped)
        swap(prev1, prev2);

        int ans = INT_MAX;

        if(n1[index]>prev1 && n2[index]>prev2)
        // no swap
        ans = solverec(n1,n2,index+1,false);

        if(n1[index] >prev2 && n2[index] > prev1)
        // swap
        ans = min(ans, 1 + solverec(n1,n2, index+1, true));

        return ans;

    }

    int solveMem(vector<int>& n1, vector<int>& n2, int index, int swapped, vector<vector<int>>& dp)
    {
        if(index >= n1.size())
        return 0;

        if(dp[index][swapped] != -1)
        return dp[index][swapped];
        
        int prev1 = n1[index-1];
        int prev2 = n2[index-1];

        if(swapped)
        swap(prev1, prev2);

        int ans = INT_MAX;

        if(n1[index]>prev1 && n2[index]>prev2)
        // no swap
        ans = solveMem(n1,n2,index+1,0,dp);

        if(n1[index] >prev2 && n2[index] > prev1)
        // swap
        ans = min(ans, 1 + solveMem(n1,n2, index+1, 1,dp));

        dp[index][swapped] = ans;

        return dp[index][swapped];

    }

    int solvetab(vector<int>& n1, vector<int>& n2)
    {
        vector<vector<int>> dp(n1.size()+1, vector<int>(2,0));
        int n = n1.size();
        
        for(int index = n-1; index>= 1; index--)
        {
            for(int swapped = 1; swapped >=0; swapped--)
            {
                 int prev1 = n1[index-1];
                 int prev2 = n2[index-1];

                if(swapped)
                swap(prev1, prev2);

                int ans = INT_MAX;

                if(n1[index]>prev1 && n2[index]>prev2)
                // no swap
                ans = dp[index+1][0];

                if(n1[index] >prev2 && n2[index] > prev1)
                // swap
                ans = min(ans, 1 + dp[index+1][1]);

                dp[index][swapped] = ans;

            }
        }
        
        return dp[1][0];
    }

    int solveSO(vector<int>& n1, vector<int>& n2)
    {
        int n = n1.size();
        
        int currswap = 0;
        int currnoswap = 0;
        int swapp = 0;
        int noswap = 0;

        for(int index = n-1; index>= 1; index--)
        {
            for(int swapped = 1; swapped >=0; swapped--)
            {
                 int prev1 = n1[index-1];
                 int prev2 = n2[index-1];

                if(swapped)
                swap(prev1, prev2);

                int ans = INT_MAX;

                if(n1[index]>prev1 && n2[index]>prev2)
                // no swap
                ans = noswap;

                if(n1[index] >prev2 && n2[index] > prev1)
                // swap
                ans = min(ans, 1 + swapp);

                if(swapped)
                currswap = ans;
                else
                currnoswap = ans;

            }

            swapp = currswap;
            noswap = currnoswap;
        }
        
        return min(noswap,swapp);
    }
    int minSwap(vector<int>& n1, vector<int>& n2) {
        n1.insert(n1.begin(),-1);
        n2.insert(n2.begin(),-1);

        // return solverec(n1,n2,1,false);

        // vector<vector<int>> dp(n1.size(),vector<int> (2,-1));
        // return solveMem(n1,n2,1,0,dp);

        // return solvetab(n1,n2);

        return solveSO(n1,n2);

    }
};
93549