N couples sit in 2N seats arranged in a row and want to hold hands. We want to know the minimum number of swaps so that every couple is sitting side by side. A *swap* consists of choosing **any** two people, then they stand up and switch seats.

The people and seats are represented by an integer from `0`

to `2N-1`

, the couples are numbered in order, the first couple being `(0, 1)`

, the second couple being `(2, 3)`

, and so on with the last couple being `(2N-2, 2N-1)`

.

The couples’ initial seating is given by `row[i]`

being the value of the person who is initially sitting in the i-th seat.

**Example 1:**

Input:row = [0, 2, 1, 3]Output:1Explanation:We only need to swap the second (row[1]) and third (row[2]) person.

**Example 2:**

Input:row = [3, 2, 0, 1]Output:0Explanation:All couples are already seated side by side.

**Note:**

`len(row)`

is even and in the range of`[4, 60]`

.`row`

is guaranteed to be a permutation of`0...len(row)-1`

.

## HASHMAP SOLUTION:

class Solution(object): def minSwapsCouples(self, row): ans = 0 hashmap = {} for i in range(len(row)): hashmap[row[i]] = i for i in range(0, len(row), 2): x = row[i] if row[i+1] == x^1: continue ans += 1 part_ind = hashmap[x^1] row[i+1], row[part_ind] = row[part_ind], row[i+1] hashmap[row[part_ind]] = part_ind return ans # O(N) solution - Vinith

## UNION FIND

#### https://leetcode.com/problems/couples-holding-hands/discuss/195829/20ms-Python-UnionFind-100

- Map person index to couple index:
`x`

->`x // 2`

, so we need to move any two people that has the same couple index together. - Define a
*Double Seats*as a pair of seats that starts at even index, e.g. seats`(0, 1), (2, 3), ...`

- Using UnionFind structure, for each
*Double Seats*, union the two couple index corresponding to the two people currently seating there. - For any disjoint set in the ultimate UnionFind structure, the couples within the set can be matched by some internal swapping. If it has
`n`

couples there,`n-1`

is the number of swapping needed. - So, total number of swapping needed:
`total number of couples`

–`the number of disjoint sets`

class Solution: def minSwapsCouples(self, row: List[int]) -> int: couples = [0]*len(row) count = 0 rank = defaultdict(lambda:0) parent = {} for i,x in enumerate(row): couples[i] = x//2 for i in range(len(couples)//2): parent[i] = i def find(node): if parent[node] == node: return parent[node] parent[node] = find(parent[node]) return parent[node] def union(xroot, yroot): if rank[xroot]>rank[yroot]: parent[yroot] = xroot elif rank[yroot]>rank[xroot]: parent[xroot] = yroot else: parent[yroot] = xroot rank[xroot]+=1 for i in range(len(couples)//2): p1 = couples[2*i] p2 = couples[2*i+1] xroot = find(p1) yroot = find(p2) if xroot!=yroot: union(xroot, yroot) count+=1 return count

## Greedy Array Solution

#### https://leetcode.com/problems/couples-holding-hands/discuss/730225/Python-or-Greedy-or-Concise-or-O(n)-O(n)

class Solution: def minSwapsCouples(self, row: List[int]) -> int: i, ans, di = 0, 0, {x : i for i, x in enumerate(row)} while i < len(row): x = row[i] + (-1 if row[i] % 2 else 1) if row[i + 1] != x: row[di[x]], di[row[i + 1]], row[i + 1], di[x], ans = row[i + 1], di[x], x, i + 1, ans + 1 i += 2 return ans

#### https://leetcode.com/problems/couples-holding-hands/discuss/188064/Verbosely-commented-greedy-O(n)-Python-solution-no-hashmap

Unlike other answers, a hashmap is unnecessary: an array will take up the same space complexity but guarantee O(1) worst-case lookup/update.

Complexity: Runtime O(n), where `n`

is the length of the row.

Space O(n)

class Solution: def minSwapsCouples(self, row): """ :type row: List[int] :rtype: int """ position = [None] * len(row) # Facilitate O(1) access to which seat a particular person is sitting in. for pos, person in enumerate(row): position[person] = pos swaps = 0 for i in range(0, len(row), 2): left_person = row[i] right_person = row[i + 1] # Couples are paired up like (0,1), (2,3). Notice if a person is even # their partner is person+1. if left_person % 2 == 0: lefts_partner = left_person + 1 else: lefts_partner = left_person - 1 # left_person is not seated next to his partner; a swap needs to be done. if right_person != lefts_partner: # Move right_person where lefts_partner was. We don't need to # explicitely move lefts_partner next to left_person, because # later iterations of the loop never access or depend on # left's partner or his correct seat ever again. lefts_partner_original_position = position[lefts_partner] # right_person is moved to where left's partner was sitting. row[lefts_partner_original_position] = right_person # We update right_person's new seat number. position[right_person] = lefts_partner_original_position swaps += 1 return swaps

#### https://leetcode.com/problems/couples-holding-hands/discuss/191520/Python-beats-100

Several facts to observe:

1.For each mismatched couple, you need at most one swap to make it right. (1 swap/couple, efficiency lowerbound)

2.You can match at most two couples with one swap.(2 couple/swap, efficiency upperbound)

3.Swap one in a mismatched couple to create situation 2 does not help reduce the # of swaps needed. Its amortized efficiency is still 1 couple/swap. So it does not make sense to be smart to create situation 2.

Note that situation 2 is naturally achieved when we try to make one couple matched. So it is a just a side effect and no extra action is required.

As a result of above observations, we just simply go through the row and make every couple mathced. Skip those already matched. return the # of swaps performed.

Codewise, I have maintained a seats array to keep track such that:

seats[i] is the seat index of i in the row.

# Accepted Greedy Array Solution Solution class Solution(object): def minSwapsCouples(self, row): ans = 0 for i in range(0, len(row), 2): x = row[i] if row[i+1] == x^1: continue ans += 1 for j in range(i+1, len(row)): if row[j] == x^1: row[i+1], row[j] = row[j], row[i+1] break return ans

#### https://leetcode.com/problems/couples-holding-hands/discuss/113382/Python-greedy

Scan from left to right, if non-couple sitting in a 2 seat block, swap the one sitting on the right with the spouse of the one sitting on the left.

class Solution: def minSwapsCouples(self, row): s=[i//2 for i in row] ans=0 n=len(s) for i in range(1,n,2): if s[i]!=s[i-1]: p=s.index(s[i-1],i) s[p]=s[i] s[i]=s[i-1] ans+=1 return ans

#### https://leetcode.com/problems/couples-holding-hands/discuss/113352/python-on

class Solution(object): def minSwapsCouples(self, row): res=0 for i in range(0,len(row),2): p=row[i]+1 if row[i]%2==0 else row[i]-1 j=row.index(p) if j-i>1: row[i+1],row[j]=row[j],row[i+1] res+=1 return res

### Iterative DFS Solution

class Solution: def minSwapsCouples(self, row: List[int]) -> int: def dfs(seat): count, tmp = 0, seat while tmp in graph and graph[tmp] != seat: count += 1 visited.add(tmp) visited.add(tmp + 1 if tmp % 2 == 0 else tmp - 1) visited.add(graph[tmp]) visited.add(graph[tmp] + 1 if graph[tmp] % 2 == 0 else graph[tmp] - 1) tmp = graph[tmp] return count graph = collections.defaultdict(int) for i in range(0, len(row), 2): inum, jnum = row[i], row[i+1] rnum = inum + 1 if inum % 2 == 0 else inum - 1 lnum = jnum + 1 if jnum % 2 == 0 else jnum - 1 if jnum != rnum: graph[rnum] = jnum graph[lnum] = inum count = 0 visited = set() for i in range(len(row)): if i not in visited: count += dfs(i) return count