801. Minimum Swaps To Make Sequences Increasing

Description

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], and nums2 = [5,6,7,4], you can swap the element at i = 3 to obtain nums1 = [1,2,3,4] and nums2 = [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 <= 10⁵
nums2.length == nums1.length
0 <= nums1[i], nums2[i] <= 2 * 10⁵

Solutions

Solution 1: Dynamic Programming

Define \(a\) and \(b\) to represent the minimum number of swaps needed to make the element sequences strictly increasing up to index \([0..i]\), with the \(i\)-th element not swapped and swapped, respectively. The index starts from \(0\).

When \(i=0\), we have \(a = 0\) and \(b = 1\).

When \(i \gt 0\), we first save the previous values of \(a\) and \(b\) in \(x\) and \(y\), and then discuss the following cases:

If \(nums1[i - 1] \ge nums1[i]\) or \(nums2[i - 1] \ge nums2[i]\), to make both sequences strictly increasing, the relative positions of the elements at indices \(i-1\) and \(i\) must change. That is, if the previous position was swapped, then the current position should not be swapped, so \(a = y\); if the previous position was not swapped, then the current position must be swapped, so \(b = x + 1\).

Otherwise, the relative positions of the elements at indices \(i-1\) and \(i\) do not need to change, so \(b = y + 1\). Additionally, if \(nums1[i - 1] \lt nums2[i]\) and \(nums2[i - 1] \lt nums1[i]\), the relative positions of the elements at indices \(i-1\) and \(i\) can change, so \(a\) and \(b\) can take the smaller values, thus \(a = \min(a, y)\) and \(b = \min(b, x + 1)\).

Finally, return the smaller value between \(a\) and \(b\).

The time complexity is \(O(n)\), and the space complexity is \(O(1)\).

Python3JavaC++GoTypeScript

class Solution:
    def minSwap(self, nums1: List[int], nums2: List[int]) -> int:
        a, b = 0, 1
        for i in range(1, len(nums1)):
            x, y = a, b
            if nums1[i - 1] >= nums1[i] or nums2[i - 1] >= nums2[i]:
                a, b = y, x + 1
            else:
                b = y + 1
                if nums1[i - 1] < nums2[i] and nums2[i - 1] < nums1[i]:
                    a, b = min(a, y), min(b, x + 1)
        return min(a, b)

class Solution {
    public int minSwap(int[] nums1, int[] nums2) {
        int a = 0, b = 1;
        for (int i = 1; i < nums1.length; ++i) {
            int x = a, y = b;
            if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
                a = y;
                b = x + 1;
            } else {
                b = y + 1;
                if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                    a = Math.min(a, y);
                    b = Math.min(b, x + 1);
                }
            }
        }
        return Math.min(a, b);
    }
}

class Solution {
public:
    int minSwap(vector<int>& nums1, vector<int>& nums2) {
        int a = 0, b = 1, n = nums1.size();
        for (int i = 1; i < n; ++i) {
            int x = a, y = b;
            if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
                a = y, b = x + 1;
            } else {
                b = y + 1;
                if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                    a = min(a, y);
                    b = min(b, x + 1);
                }
            }
        }
        return min(a, b);
    }
};

func minSwap(nums1 []int, nums2 []int) int {
    a, b, n := 0, 1, len(nums1)
    for i := 1; i < n; i++ {
        x, y := a, b
        if nums1[i-1] >= nums1[i] || nums2[i-1] >= nums2[i] {
            a, b = y, x+1
        } else {
            b = y + 1
            if nums1[i-1] < nums2[i] && nums2[i-1] < nums1[i] {
                a = min(a, y)
                b = min(b, x+1)
            }
        }
    }
    return min(a, b)
}

function minSwap(nums1: number[], nums2: number[]): number {
    let [a, b] = [0, 1];
    for (let i = 1; i < nums1.length; ++i) {
        let x = a,
            y = b;
        if (nums1[i - 1] >= nums1[i] || nums2[i - 1] >= nums2[i]) {
            a = y;
            b = x + 1;
        } else {
            b = y + 1;
            if (nums1[i - 1] < nums2[i] && nums2[i - 1] < nums1[i]) {
                a = Math.min(a, y);
                b = Math.min(b, x + 1);
            }
        }
    }
    return Math.min(a, b);
}

801. Minimum Swaps To Make Sequences Increasing

Description

Solutions

Solution 1: Dynamic Programming

Comments