Case study: Mock interview - 801. Minimum Swaps To Make Sequences Increasing

 The interviewee chose to work on dynamic programming algorithm. She had super good performance, and I like to learn better from her idea. 

Here is the gist. 

	const _ = require('lodash');
	function sayHello() {
	console.log('Hello, World');
	}
	_.times(5, sayHello);
	/*
	Your previous Plain Text content is preserved below:
	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].
	Case 1:
	A = [7,1,2]
	B = [0,5,7]
	backtracking
	A = [1,3,5,4],
	B = [1,2,3,7]
	1 3 5
	1 2 3
	2 3
	3 5
	A = [1, 3, 10, 5, 7]
	B = [1, 2, 4, 12, 14]
	A = [1, 3, 8]
	and
	B = [2, 7, 4]
	dp _ _ _
	[1,2,0] [3,7,0] [8,4,1]
	[2,1,1] [7,3,1] [4,8,1]
	i 0 1 2
	return min(dp[lastindex][0][2])
	dp[i] [A[i], B[i], minSwap]
	[B[i], A[i], minSwap]
	At index i,
	no swap: [A[i], B[i]]
	find minSwap in dp[i-1] seq in increasing order
	if possible, push dp[i] an element [A[i], B[i], minSwap+1]
	swap: [B[i], A[i]]
	*/
	//Time : O(n) Space: O(n)
	let minSwap = (A, B) => {
	let N = A.length;
	let dp = Array(N);
	dp[0] = [[A[0], B[0], 0], [B[0], A[0], 1]];
	for(let i = 1; i<N; i++){
	dp[i] = [];
	let noSwap = [A[i], B[i], +Infinity];
	for(let [prevA, prevB, prevMinSwap] of dp[i-1]){
	if(noSwap[0] > prevA && noSwap[1] > prevB){
	noSwap[2] = Math.min(noSwap[2], prevMinSwap);
	}
	}
	dp[i].push(noSwap);
	let swap = [B[i], A[i], +Infinity];
	for(let [prevA, prevB, prevMinSwap] of dp[i-1]){
	if(swap[0] > prevA && swap[1] > prevB){ // statement ?
	swap[2] = Math.min(swap[2], prevMinSwap + 1); // swap B[i] and
	}
	}
	dp[i].push(swap);
	}
	return Math.min(dp[N-1][0][2], dp[N-1][1][2]);
	}
	let A = [1, 3, 8];
	let B = [2, 7, 4];
	console.log("min swap: ", minSwap(A, B));
	A = [1,3,5,4]
	B = [1,2,3,7]
	console.log("min swap: ", minSwap(A, B));
	A = [1, 3, 10, 5, 7]
	B = [1, 2, 4, 12, 14]
	console.log("min swap: ", minSwap(A, B));

view raw 801MinimumSwapsToMakeSequencesIncreasing.js hosted with ❤ by GitHub