Given an array of 2N integers which denotes the current position of a group of people. The person (1, 2), (3, 4), (5, 6) ..... are couples. We want each couple sits next to each other. Find the minimum number of swaps needed to do this.
constraints: N <= 500
@vijju123 @l_returns @taran_1407 @vivek_1998299 please help!
Good question 
Source ?
My friend was asked this question during his interview with some company. I guess codenation (not sure).
Truely speaking the constraint that I have kept is not provided by him. He just told me that interviewer was fine with O(N^3) solution.
Is it like you have an array of numbers from 1 to N sitting on a linear table? I think this is a Codeforces question and greedy applied here. If the table is circular, the question gets tougher.
Any proof why will greedy works if it is an Array even ?
And if you have any idea how will we solve this if the table is round ?
Isn’t it the same as counting minimum number of inversions require in an array?
No, because (1, 2) can take the position of (3, 4) or any other pair…
I think Greedy solution will also work in O(n)
if b[i] and b[i+1] are pairs the continue otherwise swap b[i+1] with pair of b[i]. Use hashmap to get the curr position and pair of an element.
Proof: We assume that B[i] is in correct place(anyway one of them will be in correct place). Then we can swap the pair of B[i] with B[i-1] or B[i+1] but think for B[0]…we will have only the option of swapping with B[1]. swapping with b[i+1] will produce configuration (a,b) and swapping with b[i-1] will produce (b,a)…for B[0] we can get only (a,b) configuration…to get (b,a) configuration we will have to first swap b[0] with b[1] and then swap pair of it with current b[0] which is not optimal. Hence, swapping b[i] and b[i+1] is atleast as good as swapping b[i] and b[i-1]. Now since we assume B[i] is already is in correct position we have to swap b[i+1] with pair of b[i] resulting in swap++