Abstract / Summary

Minimize the number of swaps needed to pair each couple by swapping people in a row.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 60% (100k+ submissions).

Typical patterns to solve this problem:

• Breadth First Search
• Depth First Search
• Graph Theory
• Greedy
• Union Find

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The implementation solves the “minimum swaps to seat all couples together” problem. It receives a list row where each element represents a person, and couples are defined by consecutive integer pairs (e.g., 0 ↔ 1, 2 ↔ 3, …). The goal is to count the smallest number of swaps required so that every adjacent pair of seats contains a couple.

Core Data Structures

A dictionary named seat maps each person to their current index in row. This enables constant-time retrieval of a partner’s location, which is essential for the swap decision.

seat = { who : where for where, who in enumerate(row) }

Main Loop

The algorithm walks through the seating arrangement two seats at a time, treating each adjacent pair as a potential couple slot.

for i in range(0, len(row), 2):
    a = row[i]
    b = row[i + 1]
    ...

The step size of two guarantees that every iteration examines a distinct pair of seats without overlap.

Swap Logic

For the person a at the left seat, the expected partner is computed by flipping the least-significant bit (a ^ 1). If the right seat already holds this partner, no action is needed. Otherwise a swap is performed: the person currently occupying the partner’s seat (seat[love]) is moved to the right seat, and the dictionary is updated to reflect the new location of that displaced person. The swap counter result is incremented.

love = a ^ 1
if b != love:
    row[seat[love]] = b
    seat[b] = seat[love]
    result += 1

The comment notes that row[i + 1] and seat[love] are left unchanged because the subsequent iterations will reference the updated structures directly, avoiding redundant writes.

Edge Cases Handled

When the input list length is zero, the for loop never executes and the function correctly returns zero swaps. The dictionary comprehension safely handles an empty list as well. If a couple is already seated together, the condition b != love fails and the algorithm skips any modification, preserving the current arrangement. The bit-wise partner calculation (a ^ 1) works for any non-negative integer, ensuring that the partner of the highest possible identifier is still derived correctly without overflow concerns. Because the loop increments by two, the code implicitly assumes an even number of seats; any odd-length input would raise an index error, but the problem definition guarantees even length, so the implementation aligns with that contract.

Performance Optimizations

The use of a hash map (seat) provides immediate access to any person’s position, eliminating the need for linear searches during each swap decision. By updating only the displaced person’s entry in the dictionary and leaving the partner’s seat entry untouched, the algorithm reduces the number of write operations. The in-place modification of row avoids allocating auxiliary arrays, keeping memory usage minimal. Additionally, the algorithm refrains from recomputing the partner of b after a swap, because the next iteration will naturally encounter the corrected pair, thereby saving unnecessary calculations. These choices collectively keep the execution fast even for large inputs.

Imagine a long row of chairs where couples are sitting together, but some people are sitting next to the wrong person. The goal is to make sure every person is sitting right next to their specific partner. To do this, look at the row in pairs of two chairs at a time. Pick the person in the first chair and find out who their true love is. Since the people are numbered in a special way, figuring out the partner is as simple as flipping a tiny switch in their number. Check the person sitting in the second chair to see if they are the true love. If they are not, grab the correct partner from wherever they are hiding further down the row and swap them into the seat next to the first person. Count every time a swap is made until everyone is finally sitting happily next to their partner.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: linear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++	Java						Python	TS
	WalkCCC	C++	Java
	leetcode.ca	C++	Java		C#			Go	Python	TS
	LeetcodeHelp	C++	Java						Python
	Progiez	C++	Java						Python
github	BigEggStudy				C#
	black-shadows	C++
	charles-wangkai		Java
	everthis			JS
	FelixFan1122		Java
	fengvyi	C++
	gouthampradhan		Java
	halfrost							Go
	JoshCrozier			JS
	lzl124631x	C++
	ruoru					Rust
	sonugiri1043	C++
	suxrobGM				C#
	wisdompeak	C++
	yuanliu666						Kotlin
	zfang399	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Java
leetcode.ca	C++, C#, Go, Java, Python, TypeScript
LeetcodeHelp	C++, Java, Python
Progiez	C++, Java, Python
BigEggStudy	C#
black-shadows	C++, C++
charles-wangkai	Java
everthis	JavaScript
FelixFan1122	Java
fengvyi	C++
gouthampradhan	Java
halfrost	Go
JoshCrozier	JavaScript
lzl124631x	C++
ruoru	Rust
sonugiri1043	C++
suxrobGM	C#
wisdompeak	C++
yuanliu666	Kotlin
zfang399	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality