765. Couples Holding Hands

leetcode hard

#array#backtracking#csharp#greedy#hard#leetcode#math

Task

Есть n пар, сидящих на 2n местах, расположенных в ряд, и они хотят держаться за руки.

Люди и места представлены массивом целых чисел row, где row[i] — это ID человека, сидящего на i-м месте. Пары пронумерованы по порядку: первая пара — (0, 1), вторая пара — (2, 3) и так далее, до последней пары — (2n - 2, 2n - 1).

Верните минимальное количество перестановок, чтобы каждая пара сидела рядом. Перестановка состоит из выбора любых двух человек, которые встают и меняются местами.

Пример:

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

Output: 1

Explanation: We only need to swap the second (row[1]) and third (row[2]) person.

C# solution

matched/original

public class Solution {
    int N;
    int[][] pairs;
    public int MinSwapsCouples(int[] row) {
        N = row.Length / 2;
        pairs = new int[N][];
        for (int i = 0; i < N; ++i) {
            pairs[i] = new int[2];
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return Solve(0);
    }
    public void Swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }
    public int Solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return Solve(i + 1);
        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }
        Swap(i, 1, jx, kx);
        int ans1 = 1 + Solve(i + 1);
        Swap(i, 1, jx, kx);
        Swap(i, 0, jy, ky);
        int ans2 = 1 + Solve(i + 1);
        Swap(i, 0, jy, ky);
        return Math.Min(ans1, ans2);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    int N;
    int[][] pairs;
    public int MinSwapsCouples(vector<int>& row) {
        N = row.size() / 2;
        pairs = new int[N][];
        for (int i = 0; i < N; ++i) {
            pairs[i] = new int[2];
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return Solve(0);
    }
    public void Swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }
    public int Solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return Solve(i + 1);
        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }
        Swap(i, 1, jx, kx);
        int ans1 = 1 + Solve(i + 1);
        Swap(i, 1, jx, kx);
        Swap(i, 0, jy, ky);
        int ans2 = 1 + Solve(i + 1);
        Swap(i, 0, jy, ky);
        return min(ans1, ans2);
    }
}

Java solution

matched/original

class Solution {
    int N;
    int[][] pairs;

    public int minSwapsCouples(int[] row) {
        N = row.length / 2;
        pairs = new int[N][2];
        for (int i = 0; i < N; ++i) {
            pairs[i][0] = row[2 * i] / 2;
            pairs[i][1] = row[2 * i + 1] / 2;
        }
        return solve(0);
    }

    public void swap(int a, int b, int c, int d) {
        int t = pairs[a][b];
        pairs[a][b] = pairs[c][d];
        pairs[c][d] = t;
    }

    public int solve(int i) {
        if (i == N) return 0;
        int x = pairs[i][0], y = pairs[i][1];
        if (x == y) return solve(i + 1);

        int jx = 0, kx = 0, jy = 0, ky = 0;
        for (int j = i + 1; j < N; ++j) {
            for (int k = 0; k <= 1; ++k) {
                if (pairs[j][k] == x) { jx = j; kx = k; }
                if (pairs[j][k] == y) { jy = j; ky = k; }
            }
        }

        swap(i, 1, jx, kx);
        int ans1 = 1 + solve(i + 1);
        swap(i, 1, jx, kx);

        swap(i, 0, jy, ky);
        int ans2 = 1 + solve(i + 1);
        swap(i, 0, jy, ky);

        return Math.min(ans1, ans2);
    }
}

JavaScript solution

matched/original

class Solution {
    minSwapsCouples(row) {
        this.N = row.length / 2;
        this.pairs = Array.from({ length: this.N }, (_, i) => [Math.floor(row[2 * i] / 2), Math.floor(row[2 * i + 1] / 2)]);
        return this.solve(0);
    }

    swap(a, b, c, d) {
        const t = this.pairs[a][b];
        this.pairs[a][b] = this.pairs[c][d];
        this.pairs[c][d] = t;
    }

    solve(i) {
        if (i === this.N) return 0;
        const x = this.pairs[i][0], y = this.pairs[i][1];
        if (x === y) return this.solve(i + 1);

        let jx = 0, kx = 0, jy = 0, ky = 0;
        for (let j = i + 1; j < this.N; ++j) {
            for (let k = 0; k <= 1; ++k) {
                if (this.pairs[j][k] === x) { jx = j; kx = k; }
                if (this.pairs[j][k] === y) { jy = j; ky = k; }
            }
        }

        this.swap(i, 1, jx, kx);
        const ans1 = 1 + this.solve(i + 1);
        this.swap(i, 1, jx, kx);

        this.swap(i, 0, jy, ky);
        const ans2 = 1 + this.solve(i + 1);
        this.swap(i, 0, jy, ky);

        return Math.min(ans1, ans2);
    }
}

Python solution

matched/original

class Solution:
    def minSwapsCouples(self, row: List[int]) -> int:
        self.N = len(row) // 2
        self.pairs = [[0, 0] for _ in range(self.N)]
        for i in range(self.N):
            self.pairs[i][0] = row[2 * i] // 2
            self.pairs[i][1] = row[2 * i + 1] // 2
        return self.solve(0)
    
    def swap(self, a: int, b: int, c: int, d: int):
        self.pairs[a][b], self.pairs[c][d] = self.pairs[c][d], self.pairs[a][b]
    
    def solve(self, i: int) -> int:
        if i == self.N:
            return 0
        x, y = self.pairs[i]
        if x == y:
            return self.solve(i + 1)
        
        jx, kx, jy, ky = 0, 0, 0, 0
        for j in range(i + 1, self.N):
            for k in range(2):
                if self.pairs[j][k] == x:
                    jx, kx = j, k
                if self.pairs[j][k] == y:
                    jy, ky = j, k
        
        self.swap(i, 1, jx, kx)
        ans1 = 1 + self.solve(i + 1)
        self.swap(i, 1, jx, kx)
        
        self.swap(i, 0, jy, ky)
        ans2 = 1 + self.solve(i + 1)
        self.swap(i, 0, jy, ky)
        
        return min(ans1, ans2)

Go solution

matched/original

type Solution struct {
    N     int
    pairs [][]int
}

func (s *Solution) minSwapsCouples(row []int) int {
    s.N = len(row) / 2
    s.pairs = make([][]int, s.N)
    for i := 0; i < s.N; i++ {
        s.pairs[i] = []int{row[2*i] / 2, row[2*i+1] / 2}
    }
    return s.solve(0)
}

func (s *Solution) swap(a, b, c, d int) {
    t := s.pairs[a][b]
    s.pairs[a][b] = s.pairs[c][d]
    s.pairs[c][d] = t
}

func (s *Solution) solve(i int) int {
    if i == s.N {
        return 0
    }
    x, y := s.pairs[i][0], s.pairs[i][1]
    if x == y {
        return s.solve(i + 1)
    }

    var jx, kx, jy, ky int
    for j := i + 1; j < s.N; j++ {
        for k := 0; k <= 1; k++ {
            if s.pairs[j][k] == x {
                jx, kx = j, k
            }
            if s.pairs[j][k] == y {
                jy, ky = j, k
            }
        }
    }

    s.swap(i, 1, jx, kx)
    ans1 := 1 + s.solve(i+1)
    s.swap(i, 1, jx, kx)

    s.swap(i, 0, jy, ky)
    ans2 := 1 + s.solve(i+1)
    s.swap(i, 0, jy, ky)

    if ans1 < ans2 {
        return ans1
    }
    return ans2
}