765. Couples Holding Hands

Problem Statement

Couples Holding Hands - LeetCode

Pattern:

---

Solution

class Solution {
	public void swap(int[] x, int a, int b) {
		int t = x[a];
		x[a] = x[b];
		x[b] = t;
	}
	
	public int findIndex(int[] arr, int start, int key) {
		for (; start < arr.length; start++)
			if (arr[start] == key)
				break;
		return start;
	}
	
	public int minSwapsCouples(int[] row) {
		int swapcount = 0;
		// iterate over pairs in arr
		// row.length-2 last pair is already sorted
		for (int i = 0; i < row.length-2; i += 2) {
			// find correct pair value
			int pval = row[i] % 2 == 0 ? row[i] + 1 : row[i] - 1;
 
			// if row[i+1] is wrong pair
			if (row[i+1] != pval) {
				// find correct pairIndex
				int ctPairIndex = findIndex(row, i + 2, pval);
				// swap row[i+1] with correct pair
				swap(row, i + 1, ctPairIndex);
				swapcount++;
			}
		}
		return swapcount;
	}
}

Notes

• Iterate over first el of each pair
  • check if it’s pair is correct
  • if not
    • find correct pair and swap
• it is not sufficient that Math.abs(row[i+1] - row[i]) == 0
  • 0, 1 is a pair 1, 2 isn’t