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:
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:
@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) # (2) visited=[False]*len(Ap) min_swaps=0 for i in range(len(Ap)): # (3) if not visited[i] and i!=Ap[i]: # (5) cycleLength=0 j=i while not visited[j]: visited[j]=True cycleLength += 1 # (6) j=Ap[j] min_swaps += cycleLength-1 # (7) return min_swaps ``
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.