[C++] Dynamic programming with O(n) Time and O(n) Space
We easily see that the position of any element of the two provided arrays is fixed, either we choose to swap it or keep it as original. Thus, at any position th
We easily see that the position of any element of the two provided arrays is fixed, either we choose to swap it or keep it as original. Thus, at any position there are 2 states we can maintain, I call them **keep** and **swap** (keep if we choose to keep the elements as original, and swap is the opposite case).\n\nAt any position we can choose to keep it as original if the value of the element of **nums1** greater than the previous one in the same array, the same for the element of **nums2**. In the other hand, we can choose to swap the elements of the 2 arrays if and only if the value of the element of **nums1** is greater than the element of **nums2** which has position less than position of the mentioned element of **nums1** array.\n\nAs the statement of this problem, we need to make the 2 provided arrays **strictly increasing**. And they guaranteed that the test case we received is always possible to find the minimum result. Therefore, there are at least one state we can choose at any position (**keep** or **swap** the elements). \n\nWe can use the dynamic programming technique to solve this problem. The base state is at position 0 and the result is the minimum value of 2 state of the last.\n\nHere is the code:\n\n```\nint minSwap(vector<int>& nums1, vector<int>& nums2) {\n\tint n=nums1.size();\n\tvector<int> swap(n, INT_MAX), keep(n, INT_MAX);\n\n\tkeep[0]=0;\n\tswap[0]=1;\n\n\tfor(int i=1; i<n; i++) {\n\t\tif(nums1[i]>nums1[i-1] && nums2[i]>nums2[i-1]) {\n\t\t\tkeep[i]=keep[i-1];\n\t\t\tswap[i]=swap[i-1]+1;\n\t\t} \n\t\tif(nums1[i]>nums2[i-1] && nums2[i]>nums1[i-1]) {\n\t\t\tkeep[i]=min(swap[i-1],keep[i]);\n\t\t\tswap[i]=min(keep[i-1]+1,swap[i]);\n\t\t}\n\t}\n\n\treturn min(keep[n-1],swap[n-1]);\n}\n```\n\n\tTime complexity: O(n)\n\tSpace complexity: O(n)
['Dynamic Programming', 'C']