[C] Non-DP easy-to-understand O(n) solution O(1) space
The DP solution is difficult to figure out. Below is my solution.\n\nFor the input arrays A, B of length n, denoted by problem (A, B, n), define an index e to b
The DP solution is difficult to figure out. Below is my solution.\n\nFor the input arrays A, B of length n, denoted by problem (A, B, n), define an index e to be "good" if e=0 OR min{A[e], B[e]} > max{A[e-1], B[e-1]}. Whether or not to swap a "good" index e is not affected by the subarrays [0 ... e-1].\n\nFor the example A = [0, 4, 4, 5, 9] and B = [0, 1, 6, 8, 10], there are 3 "good" indices, 0, 1, and 4. The observation below is key to solving the problem:\n\nSuppose there are *k* good indices for the given problem (A, B, n), denoted by e0 = 0, e1, ... e_{k-1}, 1 <= k <= n, then the subarrays A[e_i ... e_{i+1}-1], B[e_i ... e_{i+1}-1] are completely determined once A[e_i] and B[e_i] are fixed. It can be proved by induction.\n\nSo, for each pair of subarrays e_i, ..., e_{i+1}-1, there are two possible ways to make them increasing, namely, swap and not swap A[e_i], B[e_i]. Denoted them by P1 and P2. In practice, we only need to solve one of them because of the following relation:\n\nNumber of swaps of P1 + Number of swaps of P2 = subarray length.\n\nWe solve the problem by adding the solution to each subproblem confined to e_i, ... e_{i+1}-1. Running time is Theta(n).\n```\n#define MIN(a, b) (a <= b? a : b)\n#define MAX(a, b) (a >= b? a : b)\n\nint minSwap(int* A, int ASize, int* B, int BSize){\n    int ans = 0;\n    int e = 0; // the max. good index before the current iteration i\n    int curSwaps = 0; // record no. of swaps in the current subproblem\n    for (int i = 1; i < ASize; i++) {\n        if (MIN(A[i], B[i]) > MAX(A[i-1], B[i-1])) { // if i is a good index\n            ans += MIN(curSwaps, i-e-curSwaps); // select min. swaps of the two configurations\n            e = i;\n            curSwaps = 0;\n            continue;\n        }\n        if (A[i-1] >= A[i] || B[i-1] >= B[i]) { // if need to swap i\n            int temp = A[i];\n            A[i] = B[i];\n            B[i] = temp;\n            curSwaps++;\n        }\n    } // end for\n    ans += MIN(curSwaps, ASize-e-curSwaps);\n    return ans;\n}\n```
['C']