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++