Can u plz give me a nice explanation on Couple holding hands leetcode
Doubt on leetcode problem
Some basic observations and initial transformations.
- After all the moves, in the final arrangement, the person sitting on first seat will be paired with second seat, 3rd seat with 4th seat, 5th seat with 6th seat and so on.
So let’s pair these up and replace each such pair with a single node. Since there and 2n seats, there will be n nodes. - Let’s replace [0,1] with [0,0], [2,3] with 1 and so on. This simplifies the problem without any change to the final answer.
Solution :
Try to see the case where we won’t have to make any moves. For example one such arrangement can be like this ->
There are 6 people in total, so 3 pairs. And they are sitting from the start like [0,0][1,1][2,2] or [1,1][0,0][2,2], etc.
SO what I am trying to say is we are trying to reaching a state where each node is composed of single pair. If we have an arrangement like this [0,1][1,0][2,2] we need to make one swap and make it [0,0][1,1][2,2].
The way we can do this is start forming undirected edges between different nodes if they have members from the same pair.
In the above example we make an edge in first node and second node and back from 2nd to first node.
You will see that we always form a cycle. Basically graph can be divided into several components with each component being a cycle. Each component can be solved independently and you need to add component size - 1 to variable swaps, which sums up to N-(number of components).
This is how you have to approach this.
I would advise you to reread this explanation if you don’t get it and form sample testcases and try to understand what I am trying to say.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.