<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>

int dp[100010][2]; 
// [100010]   -> to keep track of current index 
// [2]        -> to check last index swapped or not 

int rec(vector<int> &p,vector<int> &q,int idx,bool prev)
{
    if(idx==p.size()) return 0;
    int ans = 1e6; // some big number 
    
    if(dp[idx][prev] != -1) return dp[idx][prev]; // memoization
    
    int prevP , prevQ; // previous element for both p and q vectors
    if(idx!=0)
    {
        if(prev) // it means previous index was swapped 
        {
            prevP = q[idx-1];
            prevQ = p[idx-1];
        }else 
        {
            prevP = p[idx-1];
            prevQ = q[idx-1];
        }
    }

    if(idx!=0) // returning big number for cases where nothing can be done 
    {
        if( (prevP >= p[idx] || prevQ >= q[idx] ) && (prevQ >= p[idx] || prevP >= q[idx]) ) return 1e6;
    }


    if(idx==0)
    {
        ans = min(ans,rec(p,q,idx+1,false)); // No Swap
        ans = min(ans,1+rec(p,q,idx+1,true)); // Swap
    }else
    {
        if( (prevP < p[idx] && prevQ < q[idx]) && (prevQ < p[idx] && prevP < q[idx]) )   
        {
            // IF we swap or not this idx does not have any problem So
            ans = min(ans,rec(p,q,idx+1,false));  // No Swap
            ans = min(ans,1+rec(p,q,idx+1,true)); // Swap
        }else if(  prevP >= p[idx] || prevQ >= q[idx] )
        {
            // Swap is must 
            ans = min(ans,1+rec(p,q,idx+1,true)); // Swap 
        } else 
        {
            // No need to swap 
            ans = min(ans,rec(p,q,idx+1,false));
        }
    }

    return dp[idx][prev] = ans;
}




class Solution {
public:
    int minSwap(vector<int>& p, vector<int>& q) 
    {
        ios_base::sync_with_stdio(false); cin.tie(NULL);
        memset(dp,-1,sizeof(dp));
        return rec(p,q,0,false);   
    }
};
101476