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: 1
Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

Example 2:

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

Note:

  1. len(row) is even and in the range of [4, 60].
  2. 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

  1. Map person index to couple index: x -> x // 2, so we need to move any two people that has the same couple index together.
  2. Define a Double Seats as a pair of seats that starts at even index, e.g. seats (0, 1), (2, 3), ...
  3. Using UnionFind structure, for each Double Seats, union the two couple index corresponding to the two people currently seating there.
  4. 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.
  5. 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 O(n)

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

Leave a reply