C++, O(n), With detailed explanation
\n\n\tint minSwap(vector& nums1, vector& nums2) {\n        /\n        At any index i, min number of swaps to maintain 0 to i in order = \n            min(minimu
\n\n\tint minSwap(vector<int>& nums1, vector<int>& nums2) {\n        /*\n        At any index i, min number of swaps to maintain 0 to i in order = \n            min(minimum number of swaps required to maintain 0 to i in order by swapping ith numbers, \n                minimum number of swaps required to maintain 0 to i in order by not swapping ith numbers)\n        \n        if we maintain these 2 variables for every index i, then we can easily find the answer for n.\n        \n        Following cases arises:\n        1. Numbers are already in order. Swapping again disturbs the order:\n           Since, swapping only ith distubs the order, if we need to swap ith, we must also swap i-1th\n                      \n        2. Numbers are already in order. Swapping again does not matter.\n           Since swapping ith again does not matter, if we swap ith, previous numbers can be swapped or \n           not swapped. Find the min of 2 cases.\n           If we do not swap ith, since i-1th can be swapped or not swapped, find the min of 2 cases.\n           \n        3. Numbers are not in order. We must swap to order.\n           Since we need to swap ith to make order, i-1th cannot be swapped. \n        \n        In the code below, \n        prevSwap - min number of swaps by swapping i-1th to keep 0 to i-1 in order\n        prevNoSwap - min number of swaps by not swapping i-1th to keep 0 to i-1 in order\n        */\n        int prevSwap = 1, prevNoSwap = 0;\n        for (int i = 1; i<nums1.size(); i++) {\n            int curSwap = 0, curNoSwap = 0;\n            \n            // case: already in the proper order\n            if (nums1[i-1] < nums1[i] && nums2[i-1] < nums2[i]) {\n                \n                // case 2: if we swap ith, it do not disturb the order, so find the min of both case\n                if (nums1[i] > nums2[i-1] && nums2[i] > nums1[i-1]) {\n                    // if we swap ith, i-1th can be swapped or not swapped. In both cases order is maintained; \n                    // so find min of the two cases\n                    curSwap = min(prevNoSwap, prevSwap) + 1;\n                    // if we do not swap the ith, i-1th can be swapped or not swapped\n                    curNoSwap = min(prevSwap, prevNoSwap);\n                } else {\n                    // case 1: if we swap ith, it disturbs the order, so do not swap ith\n                    \n                    // if we have to swap ith, then we must swap i-1th also to retain the order\n                    curSwap = prevSwap + 1;\n                    // if we do not swap ith, then nothing to do for i-1th as well; count remains same as prev\n                    curNoSwap = prevNoSwap;\n                }\n            } else {\n                // case 3: order is not proper, we must swap the ith element\n                \n                // if we swap ith, we must not swap i-1th.\n                curSwap = prevNoSwap + 1;\n                // if we do not swap ith, i-1th must be swapped to maintain order\n                curNoSwap = prevSwap;\n            }\n\n            prevSwap = curSwap;\n            prevNoSwap = curNoSwap;\n        }\n        \n        return min(prevSwap, prevNoSwap);\n    }
[]