DP O(n) Solution | Recursion & Memoization | Explained with comments
\nclass Solution {\npublic:\n    \n    int solve(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& dp, int index, int max1, int max2, bool swap){\n  
```\nclass Solution {\npublic:\n    \n    int solve(vector<int>& nums1, vector<int>& nums2, vector<vector<int>>& dp, int index, int max1, int max2, bool swap){\n        if(index == nums1.size()) return 0;\n        if(dp[index][swap] != -1) return dp[index][swap];\n        \n        if(nums1[index] <= max1 || nums2[index] <= max2) //if current array not strictly increasing, then swapping is the only option\n            return dp[index][swap] = 1 + solve(nums1, nums2, dp, index + 1, nums2[index], nums1[index], true);\n        \n        //if current array is strictly increasing, try swapping and not swapping and choose minimum\n        //swap only if the array formed after swapping is then strictly increasing, else assign a very large number to avoid it in minimum\'s calculation\n        int Swap = (nums1[index] > max2 && nums2[index] > max1) ? 1 + solve(nums1, nums2, dp, index + 1, nums2[index], nums1[index], true) : 1000000;\n        int notSwap = solve(nums1, nums2, dp, index + 1, nums1[index], nums2[index], false);\n        \n        //return best of swapping and non-swapping options\n        return dp[index][swap] = min(Swap, notSwap);\n    }\n    \n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n        vector<vector<int>> dp(nums1.size() + 1, vector<int>(2, -1));\n        return min(solve(nums1, nums2, dp, 1, nums1[0], nums2[0], false), 1 + solve(nums1, nums2, dp, 1, nums2[0], nums1[0], true));\n    }\n};\n\n```
['Dynamic Programming', 'C', 'C++']