# New question - Google interview

• N different couple goes to a cinema with 2N different seats. They take their place randomly. You could make swap operation. Write a code for given input what is the minimum number of swap operations for sitting all couples with their partners? Additionally, be sure that no one swaps more than 2 times.

• Only leave the idea here.

For example, couples are a, b, c, d, e & 1, 2, 3, 4, 5. a->1, b->2 and so on.
Then fix the alphabets & try matching numbers with alphabets..
Make an Boolean array to represent if a number has been visited.
Initially all numbers have not been visited.
Find the circles recursively as this https://www.geeksforgeeks.org/minimum-number-swaps-required-sort-array/
Finally, do swap accordingly.

The complexity is:
[native]:
time: O(n) in finding all circle, O(n) in swapping (or you can do both simutaneously)
space: O(n) in Boolean array.

Any better idea?

• @pradeepkv09 Oh, I don't know... But I think this is pretty similar to this question:
https://leetcode.com/problems/couples-holding-hands/description/.

• @r97922153-gmail.com sorting requires O(n.log(n)) .. rest is O(n)

BTW here is the Python code I wrote based on awesome article you shared.

``````def minSwaps(A):
"""
Steps:
- create new list of (value,index) tuples, call it Ap   ... (1)
- sort Ap using value                                   ... (2)
Initialize min_swaps=0
- now go over Ap sequentially.                          ... (3)
say, index i is current node
- cycleLength=0
- if i is not visited yet and i'th element is not at correct position ... (5)
- tag i as visited
- count number of nodes in cycle starting from i. Assign as cycleLength ... (6)
- see from where i came from.
There is some node there. tag the node visited.
see where that came from ... and so on ...
terminate this when we loop back to i
Add cycleLength-1 to min_swaps                       ... (7)
go to (3)
"""
Ap=[(A[i],i) for i in range(len(A))] # (1)
Ap=sorted(Ap, key=lambda pair: pair[0]) # (2)
visited=[False]*len(Ap)
min_swaps=0
for i in range(len(Ap)): # (3)
if not visited[i] and i!=Ap[i][1]: # (5)
cycleLength=0
j=i
while not visited[j]:
visited[j]=True
cycleLength += 1 # (6)
j=Ap[j][1]
min_swaps += cycleLength-1 # (7)
return min_swaps
````````

• I think that is a good question

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.