Welcome to Subscribe On Youtube

Formatted question description: https://leetcode.ca/all/801.html

801. Minimum Swaps To Make Sequences Increasing

Level

Medium

Description

We have two integer sequences A and B of the same non-zero length.

We are allowed to swap elements A[i] and B[i]. Note that both elements are in the same index position in their respective sequences.

At the end of some number of swaps, A and B are both strictly increasing. (A sequence is strictly increasing if and only if A[0] < A[1] < A[2] < ... < A[A.length - 1].)

Given A and B, return the minimum number of swaps to make both sequences strictly increasing. It is guaranteed that the given input always makes it possible.

Example:

Input: A = [1,3,5,4], B = [1,2,3,7]

Output: 1

Explanation: Swap A[3] and B[3]. Then the sequences are: A = [1, 3, 5, 7] and B = [1, 2, 3, 4] which are both strictly increasing.

Note:

  • A, B are arrays with the same length, and that length will be in the range [1, 1000].
  • A[i], B[i] are integer values in the range [0, 2000].

Solution

Use dynamic programming. Use countNoSwap and countSwap to represent the minimum number of swaps such that the current element is not swapped and the current element is swapped, respectively.

Let length be the length of A and B. For i from 1 to length - 1, check the values A[i - 1], A[i], B[i - 1] and B[i]. Let curCountNoSwap and curCountSwap be the minimum number of swaps at the current index, with the same meaning as countNoSwap and countSwap. Consider the following two cases. Both cases need to be considered for each index.

  1. When A[i - 1] < A[i] and B[i - 1] < B[i]. If the numbers at index i - 1 are not swapped, the numbers at index i needn’t be swapped. If the numbers at index i - 1 are swapped, the numbers at index i need to be swapped as well. So curCountNoSwap = Math.min(curCountNoSwap, countNoSwap) and curCountSwap = Math.min(curCountSwap, countSwap + 1).
  2. When A[i - 1] < B[i] and B[i - 1] < A[i]. Then either the numbers at index i - 1 need to be swapped or the numbers at index i need to be swapped. So curCountNoSwap = Math.min(curCountNoSwap, countSwap) and curCountSwap = Math.min(curCountSwap, countNoSwap + 1).

After one index is visited, update countNoSwap = curCountNoSwap and countSwap = curCountSwap.

Finally, return the minimum of countNoSwap and countSwap.

  • class Solution {
    public int minSwap(int[] A, int[] B) {
        int countNoSwap = 0, countSwap = 1;
        int length = A.length;
        for (int i = 1; i < length; i++) {
            int curCountNoSwap = Integer.MAX_VALUE, curCountSwap = Integer.MAX_VALUE;
            if (A[i - 1] < A[i] && B[i - 1] < B[i]) {
                curCountNoSwap = Math.min(curCountNoSwap, countNoSwap);
                curCountSwap = Math.min(curCountSwap, countSwap + 1);
            }
            if (A[i - 1] < B[i] && B[i - 1] < A[i]) {
                curCountNoSwap = Math.min(curCountNoSwap, countSwap);
                curCountSwap = Math.min(curCountSwap, countNoSwap + 1);
            }
            countNoSwap = curCountNoSwap;
            countSwap = curCountSwap;
        }
        return Math.min(countNoSwap, countSwap);
    }
}

  • // OJ: https://leetcode.com/problems/minimum-swaps-to-make-sequences-increasing/
// Time: O(N)
// Space: O(N)
class Solution {
    int inf = 1e9;
    inline bool valid(vector<int>& A, vector<int>& B, int i) {
        return i == 0 || (A[i] > A[i - 1] && B[i] > B[i - 1]);
    }
    unordered_map<int, int> memo;
    int dp(vector<int> &A, vector<int>& B, int i, bool swapped = false) {
        if (i == A.size()) return 0;
        int key = swapped * 2000 + i;
        if (memo.count(key)) return memo[key];
        int cnt = valid(A, B, i) ? solve(A, B, i + 1, false) : inf;
        swap(A[i], B[i]);
        cnt = min(cnt, valid(A, B, i) ? 1 + solve(A, B, i + 1, true) : inf);
        swap(A[i], B[i]);
        return memo[key] = cnt;
    }
public:
    int minSwap(vector<int>& A, vector<int>& B) {
        return dp(A, B, 0);
    }
};

  • 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(object):
    def minSwap(self, A, B):
        """
        :type A: List[int]
        :type B: List[int]
        :rtype: int
        """
        N = len(A)
        keep = [float('inf')] * N
        swap = [float('inf')] * N
        keep[0] = 0
        swap[0] = 1
        for i in range(1, N):
            if A[i] > A[i - 1] and B[i] > B[i - 1]:
                keep[i] = keep[i - 1]
                swap[i] = swap[i - 1] + 1
            if A[i] > B[i - 1] and B[i] > A[i - 1]:
                keep[i] = min(keep[i], swap[i - 1])
                swap[i] = min(swap[i], keep[i - 1] + 1)
        return min(keep[N - 1], swap[N - 1])

  • 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)
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

All Problems

All Solutions