Minimum Swaps To Make Sequences Increasing

LeetCode Q 801 - Minimum Swaps To Make Sequences Increasing

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 :

1. State: dp[i][j] denotes the minimum steps we need to make A.substring(i - 1) is the same as B.substring(i - 1) and j represents the operation type. To let those two strings equal, we have two choices, one is swap ith char in A and B, or do nothing.

   • dp[i][0]: we don’t swap ith char in A and B.
   • dp[i][1]: we swap them.

2. state transfer fuction:
   Since this question is guaranteed to have the answer, therefore at least one of the following two conditions exists:

   1. A[i] > A[i - 1] && B[i] > B[i - 1]
   2. A[i] > B[i - 1] && B[i] > A[i - 1]

• if condition 1 exists,
  • if we don’t need to swap chars, then
    dp[i][0] = min(dp[i-1][0], dp[i][0])
  • if we still swap chars, we also need to swap (i-1)th char in A and B, then
    dp[i][1] = min(dp[i-1][1] + 1, dp[i][1])
• if condition 2 exists,
  • if we don’t need to swap chars, then we need to swap (i-1)th char in A and B, which means we can only get to dp[i][0] from dp[i-1][1], therefore
    dp[i][0] = min(dp[i-1][1], dp[i][0]))
  • if we still swap chars, we don’t need to swap (i-1)th char in A and B, then
    dp[i][1] = min(dp[i-1][0] + 1, dp[i][1])

3. boundary cases:
   dp[0][0] = 0, dp[0][1] = 1, other numbers in dp are all initialized as INF.

4. Optimization:
   Since dp[i] is only depends on dp[i-1], we can use sliding array to optimize space complexity to O(1).

Time Complexity: O(n)
Space Complexity: O(2n)

Code:

public int minSwap(int[] A, int[] B) {
	if (A == null || A.length == 0 || B == null || B.length != A.length) return 0;

	int len = A.length;
	int[][] dp = new int[len][2];

	dp[0][0] = 0; dp[0][1] = 1;
	for (int i = 1; i < len; i++) {
		dp[i][0] = dp[i][1] = Integer.MAX_VALUE;
		if (A[i] > A[i-1] && B[i] > B[i-1]) {
			dp[i][0] = Math.min(dp[i-1][0], dp[i][0]);
			dp[i][1] = Math.min(dp[i-1][1] + 1, dp[i][1]);
		}
		if (A[i] > B[i-1] && B[i] > A[i-1]) {
			dp[i][0] = Math.min(dp[i-1][1], dp[i][0]);
			dp[i][1] = Math.min(dp[i-1][0] + 1, dp[i][1]);
		}
	}

	return Math.min(dp[len-1][0], dp[len-1][1]);
}