C++ & Rust: One Pass Scan Counting Greedy O(N)
The reasining is pretty much the same essentially as most other post. \n1) Let n be the lenth of the arrays and count be the number of swaps of a way to make bo
The reasining is pretty much the same essentially as most other post. \n1) Let n be the lenth of the arrays and count be the number of swaps of a way to make both arrays strictly incresing. Alternately, we can make n - count swaps to arcgive the same goal. Therefore, the answer is min(count, n - count).\n2) As matter of fact, above conclusion is not valid if both elements at a position are greater than either elements in front of the position. One nice thing needs to be noticed is that any swap after the position has no impact. Therefore, the partial result we get up current could added to the final solution and the remaining problem could be resolved as if cuttent position is the start position.  \n3) Added Rust solution on 07/16/2022    \n~~~\n// Rust Solution\nuse std::mem;\n\nimpl Solution {\n    pub fn min_swap(nums1: Vec<i32>, nums2: Vec<i32>) -> i32 {\n        let n = nums1.len();\n        \n        let (mut nums1, mut nums2) = (nums1, nums2);\n        let (mut count, mut groupSize, mut ret) = (0, 1, 0);\n        \n        for i in 1..n {\n            if nums1[i - 1].max(nums2[i - 1]) < nums1[i].min(nums2[i]) {\n                ret += count.min(groupSize - count);\n                count = 0;\n                groupSize = 1;\n            } else {\n                groupSize += 1;\n                if nums1[i - 1] <= nums1[i] && nums2[i - 1] <= nums2[i] { continue; }\n                \n                mem::swap(&mut nums1[i], &mut nums2[i]);\n                count += 1;\n\t\t\t\t\n                if i == n - 1 { ret += count.min(groupSize - count); } \n            }\n        }\n        \n        ret\n    }\n}\n\n// C++ Solution\nclass Solution {\npublic:\n    int minSwap(vector<int>& nums1, vector<int>& nums2) {\n        int n = nums1.size(), count = 0, groupSize = 1, ret = 0;\n        for (int i = 1; i < n; ++i) {\n            int &a = nums1[i - 1], &b = nums2[i - 1], &c = nums1[i], &d = nums2[i]; \n            if (max(a, b) < min(c, d)) {\n                ret += min(groupSize - count, count);\n                count = 0;\n                groupSize = 1;\n            } else {\n                ++groupSize;\n                if (a >= c || b >= d) {\n                    swap(c, d);\n                    ++count;\n                }\n\t\t\t\tif (i == n - 1) ret += min(count, groupSize - count); \n            };\n        }\n        return ret;\n    }\n};\n~~~
['C', 'Rust']