Valentine's Matchmaker Algorithm 💖
- 8 minutes read - 1668 wordsLC765 - Couples holding hands
Problem Statement
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.
Initial solution
The below solution provides an O(n) time complexity and memory. Relatively simply, checking for every pair of people, if the left-hand side person is not seated next to its beloved, then we swap the right person next to them.
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
swap_counter = 0
person_seat = {}
for i, person in enumerate(row):
person_seat[person] = i
for j in range(0, len(row), 2):
next_person = row[j]+1 if row[j]%2 == 0 else row[j]-1
if person_seat[next_person] != j+1:
swap_counter += 1
temp_person = row[j+1]
temp_person_seat = person_seat[next_person]
row[j+1] = next_person
row[temp_person_seat] = temp_person
person_seat[next_person] = j+1
person_seat[temp_person] = temp_person_seat
return swap_counter
Maximum swap per person
While the above answer is fully correct, we notice an interesting behaviour on cases such as: [0,5,2,1,7,3,6,4]
We can seat all couples together in 3 swaps. On every one, the number 5 is pushed further and further down the array:
init:
[0, *5*, 2, 1, 7, 3, 6, 4]
[0, 1, 2, *5*, 7, 3, 6, 4]
[0, 1, 2, 3, 7, *5*, 6, 4]
[0, 1, 2, 3, 7, 6, *5*, 4]
What if we wanted to limit the number of maximum swap per person to be 1? All of a sudden our current solution breaks down.
My approach to it has been to consider that for every swap between two persons, these two had to be considered
at their correct places. Meaning out pointer j previously iterating through the array, needs to be reset to the current
position of the person who’s just been ‘swaped out’.
Why is this challenging?
A few things start to appear after resetting this j pointer.
The first assumption it breaks is that the person we’re currently looking at is not necessarily sat on a pair index.
Hence, we can’t always swap their beloved on the j+1 index. A direction needs to be considered.
The second broken assumption is that we will visit all positions.
Following the swaping cycle starting at the first index does not
guarantee all the seats will be visited in the given row. In fact, those graphs might be disconnected. If we happen to swap
out of luck a person in the correct place, then there is nowhere go next for our j pointer.
An easy test case shows this in practice: two swaps have been done placing 9 in the correct position. From there, there is nowhere to go. The algorithm exits early without considering the other paths/swaping cycles.
Init:
[10, 7, 4, 2, 3, 0, 9, 11, 1, 5, 6, 8]
[10, 11, 4, 2, 3, 0, 9, 7, 1, 5, 6, 8]
[10, 11, 4, 2, 3, 0, 6, 7, 1, 5, 9, 8]
My rather artisanal solution to identify the start of the next swaping cycle is to keep a list of visited pairs.
If we reach a point where j can’t be updated with the swaped out position because no swap has happened, then
we attempt to find the first pair of seats that were not visited and start again from there.
We’re guaranteed not to revisit already placed couples given those numbers will never be searched for a swap.
Note we have made the algorithm more complex by adding an-O(n) check operation at each loop of the while on all positions being visited - there is probably a smart way to reduce this using a counter but this is beyond the scope of this article.
class Solution:
def minSwapsCouples(self, row: List[int]) -> int:
swap_counter = 0
person_seat = {}
direction = 1
visited = [False] * len(row)
for i, person in enumerate(row):
person_seat[person] = i
j = 0
while not all(visited):
if j > len(row)-1:
# find first unvisited couple
for i in range(0, len(visited), 2):
if not visited[i]:
j = i
next_person = row[j] + 1 if row[j] % 2 == 0 else row[j] - 1
if person_seat[next_person] == j + direction:
visited[j] = visited[j + direction] = True
j += 2
continue
swap_counter += 1
temp_person = row[j + direction]
temp_person_seat = person_seat[next_person]
row[j + direction] = next_person
row[temp_person_seat] = temp_person
person_seat[next_person] = j + direction
person_seat[temp_person] = temp_person_seat
visited[j] = visited[j + direction] = True
print('swap done, new array')
print(row)
j = temp_person_seat
direction = -1 if j % 2 != 0 else 1
return swap_counter
What I find counter-intuitive with this added requirement is that we have effectively made the algorithm less performant. That-is, with regards to performing the minimum number of swaps.
The below test case illustrates it. This is the total 14 swaps done by the max-1-swap per person algorithm Algo_v2
while the initial
algorithm Algo_v1 manages in only 12 swaps. We notice seeing the couples placed after each iteration that the second algorithm,
although limiting the number of moves for each person to 1, ends-up shuffling entire couples around. This
increases the total number of swaps done.
Init:
[9,1,24,23,5,18,17,13,3,2,25,20,27,8,15,7,10,14,19,11,4,0,12,22,21,6,16,26]
Algo_v2:
[9, 8, 24, 23, 5, 18, 17, 13, 3, 2, 25, 20, 27, 1, 15, 7, 10, 14, 19, 11, 4, 0, 12, 22, 21, 6, 16, 26]
[9, 8, 24, 23, 5, 18, 17, 13, 3, 2, 25, 20, 0, 1, 15, 7, 10, 14, 19, 11, 4, 27, 12, 22, 21, 6, 16, 26]
[9, 8, 24, 23, 5, 18, 17, 13, 3, 2, 25, 20, 0, 1, 15, 7, 10, 14, 19, 11, 26, 27, 12, 22, 21, 6, 16, 4]
[9, 8, 24, 23, 16, 18, 17, 13, 3, 2, 25, 20, 0, 1, 15, 7, 10, 14, 19, 11, 26, 27, 12, 22, 21, 6, 5, 4]
[9, 8, 24, 23, 16, 17, 18, 13, 3, 2, 25, 20, 0, 1, 15, 7, 10, 14, 19, 11, 26, 27, 12, 22, 21, 6, 5, 4]
[9, 8, 24, 23, 16, 17, 18, 19, 3, 2, 25, 20, 0, 1, 15, 7, 10, 14, 13, 11, 26, 27, 12, 22, 21, 6, 5, 4]
[9, 8, 24, 23, 16, 17, 18, 19, 3, 2, 25, 20, 0, 1, 15, 7, 10, 14, 13, 12, 26, 27, 11, 22, 21, 6, 5, 4]
[9, 8, 24, 23, 16, 17, 18, 19, 3, 2, 25, 20, 0, 1, 15, 7, 22, 14, 13, 12, 26, 27, 11, 10, 21, 6, 5, 4]
[9, 8, 24, 14, 16, 17, 18, 19, 3, 2, 25, 20, 0, 1, 15, 7, 22, 23, 13, 12, 26, 27, 11, 10, 21, 6, 5, 4]
[9, 8, 15, 14, 16, 17, 18, 19, 3, 2, 25, 20, 0, 1, 24, 7, 22, 23, 13, 12, 26, 27, 11, 10, 21, 6, 5, 4]
[9, 8, 15, 14, 16, 17, 18, 19, 3, 2, 7, 20, 0, 1, 24, 25, 22, 23, 13, 12, 26, 27, 11, 10, 21, 6, 5, 4]
[9, 8, 15, 14, 16, 17, 18, 19, 3, 2, 7, 6, 0, 1, 24, 25, 22, 23, 13, 12, 26, 27, 11, 10, 21, 20, 5, 4]
[9, 8, 15, 14, 16, 17, 18, 2, 3, 19, 7, 6, 0, 1, 24, 25, 22, 23, 13, 12, 26, 27, 11, 10, 21, 20, 5, 4]
[9, 8, 15, 14, 16, 17, 3, 2, 18, 19, 7, 6, 0, 1, 24, 25, 22, 23, 13, 12, 26, 27, 11, 10, 21, 20, 5, 4]
Algo_v1:
[9, 8, 24, 23, 5, 18, 17, 13, 3, 2, 25, 20, 27, 1, 15, 7, 10, 14, 19, 11, 4, 0, 12, 22, 21, 6, 16, 26]
[9, 8, 24, 25, 5, 18, 17, 13, 3, 2, 23, 20, 27, 1, 15, 7, 10, 14, 19, 11, 4, 0, 12, 22, 21, 6, 16, 26]
[9, 8, 24, 25, 5, 4, 17, 13, 3, 2, 23, 20, 27, 1, 15, 7, 10, 14, 19, 11, 18, 0, 12, 22, 21, 6, 16, 26]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 20, 27, 1, 15, 7, 10, 14, 19, 11, 18, 0, 12, 22, 21, 6, 13, 26]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 1, 15, 7, 10, 14, 19, 11, 18, 0, 12, 20, 21, 6, 13, 26]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 26, 15, 7, 10, 14, 19, 11, 18, 0, 12, 20, 21, 6, 13, 1]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 26, 15, 14, 10, 7, 19, 11, 18, 0, 12, 20, 21, 6, 13, 1]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 26, 15, 14, 10, 11, 19, 7, 18, 0, 12, 20, 21, 6, 13, 1]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 26, 15, 14, 10, 11, 19, 18, 7, 0, 12, 20, 21, 6, 13, 1]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 26, 15, 14, 10, 11, 19, 18, 7, 6, 12, 20, 21, 0, 13, 1]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 26, 15, 14, 10, 11, 19, 18, 7, 6, 12, 13, 21, 0, 20, 1]
[9, 8, 24, 25, 5, 4, 17, 16, 3, 2, 23, 22, 27, 26, 15, 14, 10, 11, 19, 18, 7, 6, 12, 13, 21, 20, 0, 1]
Bottom-line: did I just waste a couple hours of my time trying this out? Yes, certainly.