LeetCode 765: Couples Holding Hands

Problem Description

LeetCode Problem 765

There are n couples sitting in 2n seats arranged in a row and want to hold hands.

The people and seats are represented by an integer array row where row[i] is the ID of the person sitting in the ith seat. 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).

Return 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.

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.

Constraints:

• 2n == row.length
• 2 <= n <= 30
• n is even.
• 0 <= row[i] < 2n
• All the elements of row are unique.

Difficulty: Hard

Tags: greedy, depth-first search, breadth-first search, union find, graph

Rating: 95.28%

Intuition

The key insight is that we can solve this greedily by:

1. Processing pairs of adjacent seats from left to right
2. For each pair, if they’re not a couple, find the correct partner and swap them
3. Keep track of everyone’s position for efficient lookups

This works because each swap we make puts at least one couple together, and we never need to undo a previous swap.

Solution

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row)
        swaps = 0
        # Dictionary to store each person's current position
        pos = {}
        for i, person in enumerate(row):
            pos[person] = i
            
        # Process each pair of seats
        for i in range(0, n, 2):
            current = row[i]
            # Find who should be their partner
            partner = current + 1 if current % 2 == 0 else current - 1
            
            # If wrong person is sitting next to them
            if row[i + 1] != partner:
                # Find where the partner is sitting
                partner_pos = pos[partner]
                
                # Perform the swap
                row[i + 1], row[partner_pos] = row[partner_pos], row[i + 1]
                
                # Update positions after swap
                pos[row[i + 1]] = i + 1
                pos[row[partner_pos]] = partner_pos
                
                swaps += 1
        
        return swaps

Example Walkthrough

Let’s walk through the example row = [0, 2, 1, 3]:

1. Initial state: [0, 2, 1, 3]

   • First pair: [0, 2]
   • Person 0 should be with Person 1, but they’re with Person 2

2. Find Person 1’s position (index 2)

   • Swap Person 2 and Person 1
   • After swap: [0, 1, 2, 3]
   • Swaps = 1

3. Check second pair: [2, 3]

   • Person 2 should be with Person 3
   • They’re already together
   • No swap needed

Final result: 1 swap

Complexity Analysis

• Time Complexity: $O(n)$ where n is the length of the input array

  • We make one pass through the array
  • Dictionary lookups are O(1)
  • Each position is updated at most once

• Space Complexity: $O(n)$

  • We need a dictionary to store positions of all people

Key Insights

1. The greedy approach works because:

   • Each swap directly fixes one couple
   • We never need to undo a previous swap
   • Local optimal moves lead to the global optimal solution

2. Using a position dictionary makes partner lookups $O(1)$

   • Without it, we’d need $O(n)$ searches for each swap

3. The solution is optimal because:

   • Each misplaced couple requires at least one swap
   • Our algorithm performs exactly one swap per misplaced couple