Algorithm
Problem Name: 801. Minimum Swaps To Make Sequences Increasing
You are given two integer arrays of the same length nums1 and nums2. In one operation, you are allowed to swap nums1[i] with nums2[i].
- For example, if
nums1 = [1,2,3,8], andnums2 = [5,6,7,4], you can swap the element ati = 3to obtainnums1 = [1,2,3,4]andnums2 = [5,6,7,8].
Return the minimum number of needed operations to make nums1 and nums2 strictly increasing. The test cases are generated so that the given input always makes it possible.
An array arr is strictly increasing if and only if arr[0] < arr[1] < arr[2] < ... < arr[arr.length - 1].
Example 1:
Input: nums1 = [1,3,5,4], nums2 = [1,2,3,7] Output: 1 Explanation: Swap nums1[3] and nums2[3]. Then the sequences are: nums1 = [1, 3, 5, 7] and nums2 = [1, 2, 3, 4] which are both strictly increasing.
Example 2:
Input: nums1 = [0,3,5,8,9], nums2 = [2,1,4,6,9] Output: 1
Constraints:
2 <= nums1.length <= 105nums2.length == nums1.length0 <= nums1[i], nums2[i] <= 2 * 105
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const minSwap = function(A, B) {
let swapRecord = 1, fixRecord = 0;
for (let i = 1; i < A.length; i++) {
if (A[i - 1] >= B[i] || B[i - 1] >= A[i]) {
// In this case, the ith manipulation should be same as the i-1th manipulation
// fixRecord = fixRecord;
swapRecord++;
} else if (A[i - 1] >= A[i] || B[i - 1] >= B[i]) {
// In this case, the ith manipulation should be the opposite of the i-1th manipulation
let temp = swapRecord;
swapRecord = fixRecord + 1;
fixRecord = temp;
} else {
// Either swap or fix is OK. Let's keep the minimum one
let min = Math.min(swapRecord, fixRecord);
swapRecord = min + 1;
fixRecord = min;
}
}
return Math.min(swapRecord, fixRecord);
};
Input
nums1 = [1,3,5,4], nums2 = [1,2,3,7]
Output
1