LeetCode #765: Couples Holding Hands, Greedy Partner Swaps

Brute to Best: every LeetCode problem, from the naive solution to the optimal one. In this video: The problem: N couples sit in a row of 2N seats, and couples are numbered (0,1), (2,3) and so on. Return the fewest swaps needed so every couple sits side by side. Brute force: a BFS over every possible seating, which is factorial. The key insight: fix the couches from left to right. If the person in the second seat isn't the partner, swap the partner in. Each swap fixes at least one couch, and that is optimal. The partner of x is x ^ 1. Keep a map from person to seat so each swap takes O(1). Another way: treat each couch as a node and union mismatched couples. The answer is N minus the number of components. Dry run: in 0, 2, 1, 3, swapping 2 and 1 gives 0 1 and 2 3, so the answer is 1. Complexity: O(N) time and O(N) space. Problem: https://leetcode.com/problems/couples... Related: First Missing Positive (41), Minimum Swaps to Group All 1s Together (1151), Number of Provinces (547) Full Brute to Best playlist on the channel. Subscribe for a new LeetCode problem, solved from brute force to the best solution, every day. Hashtags #leetcode #leetcode765 #coupleshlodinghands #greedy #unionfind #graph #cyclesort #hard #coding #codinginterview #dsa #python #google #faang #brutetobest