Problem

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.

OR

There are N couples sitting in a row of length 2 * N. They are currently ordered randomly, but would like to rearrange themselves so that each couple’s partners can sit side by side.

What is the minimum number of swaps necessary for this to happen?

Examples

Example 1

1
2
3

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

1
2
3

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.

Solution

Method 1 – Greedy with Position Mapping

Intuition

The key idea is to greedily swap people so that each couple sits together. For each seat pair, if the person sitting next to the current person is not their partner, swap them with the partner. Using a position map allows us to find and swap efficiently.

Approach

  1. Create a position map to track where each person is sitting.
  2. Iterate through the row in steps of 2 (each couple’s first seat):
    • For each person at index i, compute their partner (if x is even, partner is x+1; if odd, partner is x-1).
    • If the next seat does not have the partner, swap the person in the next seat with the partner.
    • Update the position map after each swap.
    • Increment the swap count.
  3. Return the total swap count.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

class Solution {
public:
    int minSwapsCouples(vector<int>& row) {
        int n = row.size();
        vector<int> pos(n);
        for (int i = 0; i < n; ++i) pos[row[i]] = i;
        int ans = 0;
        for (int i = 0; i < n; i += 2) {
            int x = row[i];
            int y = x ^ 1;
            if (row[i+1] != y) {
                int j = pos[y];
                swap(row[i+1], row[j]);
                pos[row[j]] = j;
                pos[row[i+1]] = i+1;
                ++ans;
            }
        }
        return ans;
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

func minSwapsCouples(row []int) int {
    n := len(row)
    pos := make([]int, n)
    for i, v := range row {
        pos[v] = i
    }
    ans := 0
    for i := 0; i < n; i += 2 {
        x := row[i]
        y := x ^ 1
        if row[i+1] != y {
            j := pos[y]
            row[i+1], row[j] = row[j], row[i+1]
            pos[row[j]] = j
            pos[row[i+1]] = i+1
            ans++
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

class Solution {
    public int minSwapsCouples(int[] row) {
        int n = row.length;
        int[] pos = new int[n];
        for (int i = 0; i < n; i++) pos[row[i]] = i;
        int ans = 0;
        for (int i = 0; i < n; i += 2) {
            int x = row[i];
            int y = x ^ 1;
            if (row[i+1] != y) {
                int j = pos[y];
                int tmp = row[i+1];
                row[i+1] = row[j];
                row[j] = tmp;
                pos[row[j]] = j;
                pos[row[i+1]] = i+1;
                ans++;
            }
        }
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun minSwapsCouples(row: IntArray): Int {
        val n = row.size
        val pos = IntArray(n)
        for (i in 0 until n) pos[row[i]] = i
        var ans = 0
        var i = 0
        while (i < n) {
            val x = row[i]
            val y = x xor 1
            if (row[i+1] != y) {
                val j = pos[y]
                val tmp = row[i+1]
                row[i+1] = row[j]
                row[j] = tmp
                pos[row[j]] = j
                pos[row[i+1]] = i+1
                ans++
            }
            i += 2
        }
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

class Solution:
    def minSwapsCouples(self, row: list[int]) -> int:
        n = len(row)
        pos = [0] * n
        for i, v in enumerate(row):
            pos[v] = i
        ans = 0
        for i in range(0, n, 2):
            x = row[i]
            y = x ^ 1
            if row[i+1] != y:
                j = pos[y]
                row[i+1], row[j] = row[j], row[i+1]
                pos[row[j]] = j
                pos[row[i+1]] = i+1
                ans += 1
        return ans
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

impl Solution {
    pub fn min_swaps_couples(row: Vec<i32>) -> i32 {
        let n = row.len();
        let mut row = row;
        let mut pos = vec![0; n];
        for (i, &v) in row.iter().enumerate() {
            pos[v as usize] = i;
        }
        let mut ans = 0;
        let mut i = 0;
        while i < n {
            let x = row[i];
            let y = x ^ 1;
            if row[i+1] != y {
                let j = pos[y as usize];
                row.swap(i+1, j);
                pos[row[j] as usize] = j;
                pos[row[i+1] as usize] = i+1;
                ans += 1;
            }
            i += 2;
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    minSwapsCouples(row: number[]): number {
        const n = row.length;
        const pos = Array(n);
        for (let i = 0; i < n; i++) pos[row[i]] = i;
        let ans = 0;
        for (let i = 0; i < n; i += 2) {
            const x = row[i];
            const y = x ^ 1;
            if (row[i+1] !== y) {
                const j = pos[y];
                [row[i+1], row[j]] = [row[j], row[i+1]];
                pos[row[j]] = j;
                pos[row[i+1]] = i+1;
                ans++;
            }
        }
        return ans;
    }
}

Complexity

  • ⏰ Time complexity: O(n), where n is the length of row, as each seat is visited once and swaps/updates are constant time.
  • 🧺 Space complexity: O(n), for the position map.

Method 2 -

Code

Complexity

  • ⏰ Time complexity: O(nnnxxxnnn)
  • 🧺 Space complexity: O(nnnxxx)