LeetCode Problem 765

Difficulty: 🔴 Hard
Topics: Greedy, Depth-First Search, Breadth-First Search, Union-Find, Graph Theory

Solution

LeetCode 765 - Couples Holding Hands

Problem Understanding

This problem gives us a row of seats represented by the array row, where each value is the ID of the person currently sitting in that seat. The row contains 2n people, meaning there are exactly n couples.

The couples are predefined in a very specific way:

• Person 0 is paired with 1
• Person 2 is paired with 3
• Person 4 is paired with 5
• And so on

In other words, for any person x, their partner can be computed directly:

• If x is even, their partner is x + 1
• If x is odd, their partner is x - 1

A convenient mathematical observation is:

partner = x ^ 1

because toggling the last binary bit switches between the two members of a couple.

The goal is to determine the minimum number of swaps required so that every couple sits together in adjacent seats. A swap can exchange any two people in the row, regardless of their current positions.

The important detail is that seat positions are grouped in pairs:

• Seats (0,1) form one couch
• Seats (2,3) form another couch
• Seats (4,5) form another couch

For every adjacent pair of seats, we want the two people sitting there to belong to the same couple.

The constraints are relatively small:

• 2 <= n <= 30
• Maximum row size is only 60

Even though the input size is small enough that many solutions would pass, the problem is fundamentally about recognizing structure and applying a clean greedy or graph-based strategy.

Several edge cases are important:

• The row may already be perfectly arranged, requiring zero swaps.
• Multiple couples may be cyclically misplaced, requiring careful swapping order.
• A naive strategy that swaps randomly can easily perform unnecessary operations.
• Since all elements are unique, we never need to handle duplicates or ambiguity.

Approaches

Brute Force Approach

A brute force solution would attempt to explore every possible sequence of swaps until all couples are seated together.

At each step, we could:

1. Find a pair of adjacent seats that does not contain a valid couple.
2. Try swapping one of those people with every other possible person.
3. Recursively continue until the arrangement becomes valid.
4. Track the minimum swaps seen.

This approach is correct because it explores all valid swap sequences and eventually finds the optimal one.

However, the number of possible seat arrangements grows factorially. Even for relatively small inputs, the search space becomes enormous. Backtracking with pruning may reduce the search somewhat, but it is still impractical compared to the optimal greedy solution.

Optimal Greedy Approach

The key insight is that each seat pair can be fixed independently in a greedy way.

Suppose we look at seats (i, i+1):

• Person row[i] is already fixed in place.
• We know exactly who their partner should be.
• If the partner is not already at row[i+1], then the optimal move is to swap the correct partner into seat i+1.

Why is this always optimal?

Because every valid final arrangement must place the correct partner next to row[i]. Performing that swap immediately resolves the current pair permanently without creating additional problems.

To make swaps efficient, we maintain a hash map from person ID to their current seat index. This allows us to locate any partner in constant time.

This transforms the problem into a straightforward greedy simulation.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	Exponential	O(n) to O(n!)	Tries many swap combinations recursively
Optimal Greedy	O(n)	O(n)	Fixes each seat pair independently using index mapping

Algorithm Walkthrough

Greedy + Hash Map Algorithm

1. Create a hash map called position.

This map stores the current seat index for every person. For example:

position[person] = index

We use this because we frequently need to locate a person's partner quickly. 2. Iterate through the row two seats at a time.

Since couples must occupy adjacent seats, we process indices:

0, 2, 4, 6, ...

Each iteration handles one couch. 3. Let the first person in the couch be:

first_person = row[i]

4. Compute their correct partner.

Since couples are consecutive integers:

partner = first_person ^ 1

Examples:

0 ^ 1 = 1
1 ^ 1 = 0
2 ^ 1 = 3
3 ^ 1 = 2

5. Check whether the partner is already sitting next to them.

If:

row[i + 1] == partner

then this couch is already correct, so continue. 6. Otherwise, perform one swap.

We know the partner must eventually sit at position i + 1.

Use the hash map to locate the partner:

partner_index = position[partner]

Swap:

row[i + 1], row[partner_index] = row[partner_index], row[i + 1]

7. Update the hash map.

After swapping, the moved people have new indices, so update both entries in position. 8. Increment the swap counter.

Each correction requires exactly one swap. 9. Continue until all couches are processed.

Why it works

The algorithm maintains the invariant that every processed couch is permanently correct.

When we process seats (i, i+1), person row[i] must eventually sit beside their partner in any valid solution. Swapping the correct partner directly into seat i+1 immediately fixes that couch with exactly one necessary swap.

Since fixing one couch never breaks previously fixed couches, the greedy strategy always produces the minimum number of swaps.

Python Solution

from typing import List

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row)

        # Map each person to their current seat index
        position = {}

        for index, person in enumerate(row):
            position[person] = index

        swaps = 0

        # Process each couch
        for i in range(0, n, 2):
            first_person = row[i]
            partner = first_person ^ 1

            # Already seated correctly
            if row[i + 1] == partner:
                continue

            # Find where the partner currently sits
            partner_index = position[partner]

            # Person currently sitting beside first_person
            second_person = row[i + 1]

            # Swap partner into the correct position
            row[i + 1], row[partner_index] = (
                row[partner_index],
                row[i + 1],
            )

            # Update positions after swap
            position[partner] = i + 1
            position[second_person] = partner_index

            swaps += 1

        return swaps

The implementation begins by constructing the position dictionary, which allows constant-time lookup of any person's seat index. Without this structure, each swap would require scanning the array, increasing the complexity to O(n^2).

The main loop advances two seats at a time because every pair of adjacent seats represents one couch. For each couch, the algorithm computes the correct partner using the XOR operation.

If the couch is already correct, the loop continues immediately. Otherwise, the partner's current location is retrieved from the hash map, and a swap is performed to place the partner into the correct adjacent seat.

After the swap, the dictionary must be updated carefully because two people changed positions. Failing to maintain accurate indices would cause incorrect lookups later in the algorithm.

Finally, the total number of swaps is returned.

Go Solution

func minSwapsCouples(row []int) int {
	n := len(row)

	// Map person -> current index
	position := make(map[int]int)

	for i, person := range row {
		position[person] = i
	}

	swaps := 0

	for i := 0; i < n; i += 2 {
		firstPerson := row[i]
		partner := firstPerson ^ 1

		// Already correct
		if row[i+1] == partner {
			continue
		}

		partnerIndex := position[partner]
		secondPerson := row[i+1]

		// Swap
		row[i+1], row[partnerIndex] =
			row[partnerIndex], row[i+1]

		// Update indices
		position[partner] = i + 1
		position[secondPerson] = partnerIndex

		swaps++
	}

	return swaps
}

The Go implementation follows exactly the same logic as the Python version. The primary difference is that Go uses a map[int]int for index tracking and explicit variable declarations.

Go slices are reference-like structures, so swaps directly modify the underlying array. Integer overflow is not a concern because the constraints are extremely small.

Worked Examples

Example 1

Input: row = [0,2,1,3]

Initial position map:

Person	Index
0	0
2	1
1	2
3	3

Iteration 1

Process seats (0,1):

Value	Result
first_person	0
partner	1
row[1]	2

The correct partner is not beside 0.

Find partner location:

position[1] = 2

Swap indices 1 and 2.

Row becomes:

[0,1,2,3]

Update map:

Person	Index
0	0
1	1
2	2
3	3

Swaps:

1

Iteration 2

Process seats (2,3):

Value	Result
first_person	2
partner	3
row[3]	3

Already correct.

Final answer:

1

Example 2

Input: row = [3,2,0,1]

Iteration 1

Seats (0,1):

Value	Result
first_person	3
partner	2
row[1]	2

Already correct.

Iteration 2

Seats (2,3):

Value	Result
first_person	0
partner	1
row[3]	1

Already correct.

No swaps needed.

Final answer:

0

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each person is processed at most once
Space	O(n)	Hash map stores positions of all people

The algorithm iterates through the row exactly once, processing two seats at a time. Every lookup and swap operation is constant time because of the hash map.

The auxiliary space comes entirely from the position dictionary, which stores one entry per person.

Test Cases

from typing import List

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        n = len(row)

        position = {}

        for i, person in enumerate(row):
            position[person] = i

        swaps = 0

        for i in range(0, n, 2):
            first_person = row[i]
            partner = first_person ^ 1

            if row[i + 1] == partner:
                continue

            partner_index = position[partner]
            second_person = row[i + 1]

            row[i + 1], row[partner_index] = (
                row[partner_index],
                row[i + 1],
            )

            position[partner] = i + 1
            position[second_person] = partner_index

            swaps += 1

        return swaps

solution = Solution()

assert solution.minSwapsCouples([0, 2, 1, 3]) == 1  # Simple single swap
assert solution.minSwapsCouples([3, 2, 0, 1]) == 0  # Already correct
assert solution.minSwapsCouples([0, 1, 2, 3]) == 0  # Perfect arrangement
assert solution.minSwapsCouples([1, 0, 3, 2]) == 0  # Couples reversed internally
assert solution.minSwapsCouples([0, 3, 2, 1]) == 1  # One misplaced partner
assert solution.minSwapsCouples([5, 4, 2, 6, 3, 1, 0, 7]) == 2  # Multiple swaps
assert solution.minSwapsCouples([2, 0, 1, 3]) == 1  # Swap needed at beginning
assert solution.minSwapsCouples([4, 5, 2, 3, 0, 1]) == 0  # All correct
assert solution.minSwapsCouples([7, 5, 4, 6, 1, 0, 2, 3]) == 1  # Larger input
assert solution.minSwapsCouples([9, 0, 1, 8, 2, 3, 4, 5, 7, 6]) == 1  # Near-correct large case

Test Summary

Test	Why
[0,2,1,3]	Basic example with one swap
[3,2,0,1]	Already solved arrangement
[0,1,2,3]	Perfect ascending order
[1,0,3,2]	Couples reversed but still adjacent
[0,3,2,1]	Single correction needed
[5,4,2,6,3,1,0,7]	Multiple interconnected swaps
[2,0,1,3]	Incorrect pair at front
[4,5,2,3,0,1]	Correct arrangement in different order
[7,5,4,6,1,0,2,3]	Larger mixed configuration
[9,0,1,8,2,3,4,5,7,6]	Larger near-sorted input

Edge Cases

Already Correct Seating

One important edge case occurs when every couple is already seated together. A buggy implementation might still perform unnecessary swaps if it does not properly verify adjacency before swapping.

For example:

[0,1,2,3,4,5]

The implementation handles this by immediately checking:

if row[i + 1] == partner:
    continue

No swap occurs unless the current couch is invalid.

Couples in Reverse Order

Another subtle case is when couples are seated together but reversed internally:

[1,0,3,2]

A naive implementation might incorrectly assume the smaller ID must come first.

The XOR partner computation avoids this problem completely because:

1 ^ 1 = 0
3 ^ 1 = 2

The algorithm only cares whether the correct partner is adjacent, not the order within the pair.

Cyclic Misplacement

A more difficult case occurs when several couples form a cycle of incorrect placements:

[0,2,4,1,3,5]

Here, multiple couples interfere with each other. A poor greedy strategy could perform extra swaps.

The implementation works correctly because each swap permanently fixes exactly one couch. Previously corrected couches are never broken again, guaranteeing minimal swaps.

Smallest Valid Input

The minimum input size is:

n = 2

Example:

[0,2,1,3]

The algorithm still works because the loop processes exactly one couch pair at a time and never accesses indices outside the array bounds.