Hi again
In the previous post, I wrote about how you can do it in O(n2), now we will do it in O(n).
There's a trivial solution using a hashtable but it will require O(n) extra storage, however, we will attempt to solve it without the O(n) extra storage.
Let's start thinking about how we can do it for a while.
Imagine for instance that we only have a circle and two pointers running in it. One is called "slow" and is at position "0", the other is called "fast" and moves double the speed of slow and is also at position "0". If we start moving them at their relative speeds, when will they meet? fast will complete a cycle when slow is at the middle of the lap then they will meet again at the start point when fast completes two cycles and slow will have completed only one. Now suppose fast has a head-start of "1" position before they start the race. It will meet slow "1" step before the start point", the same applies if it had a head-start of 2, 3, 4, etc.
Now to generalize, have two pointers "fast" and "slow" with fast moving the double speed of "slow" and is "k" steps ahead of slow. they will meet at "k" steps before the start point.
Back to our problem, if we start moving "fast" and "slow" from the head of the above list and consider the length of the line segment before the start of the loop to be "k". Then "slow" will be at the start of the loop while "fast" will have moved "2k" steps from the head of the list, that is, it will be "k" steps ahead of "slow". If we move both of them until they meet. we know they will meet at "k" steps before the start of the loop.
now we start a new point "slow2" and point it to the head of the list, and move it at the same speed with "slow". They will meet after "k" steps at the start of the loop. and we've got our solution in O(n) !
I will post C code for this later.
In the previous post, I wrote about how you can do it in O(n2), now we will do it in O(n).
There's a trivial solution using a hashtable but it will require O(n) extra storage, however, we will attempt to solve it without the O(n) extra storage.
Let's start thinking about how we can do it for a while.
Imagine for instance that we only have a circle and two pointers running in it. One is called "slow" and is at position "0", the other is called "fast" and moves double the speed of slow and is also at position "0". If we start moving them at their relative speeds, when will they meet? fast will complete a cycle when slow is at the middle of the lap then they will meet again at the start point when fast completes two cycles and slow will have completed only one. Now suppose fast has a head-start of "1" position before they start the race. It will meet slow "1" step before the start point", the same applies if it had a head-start of 2, 3, 4, etc.
Now to generalize, have two pointers "fast" and "slow" with fast moving the double speed of "slow" and is "k" steps ahead of slow. they will meet at "k" steps before the start point.
Back to our problem, if we start moving "fast" and "slow" from the head of the above list and consider the length of the line segment before the start of the loop to be "k". Then "slow" will be at the start of the loop while "fast" will have moved "2k" steps from the head of the list, that is, it will be "k" steps ahead of "slow". If we move both of them until they meet. we know they will meet at "k" steps before the start of the loop.
now we start a new point "slow2" and point it to the head of the list, and move it at the same speed with "slow". They will meet after "k" steps at the start of the loop. and we've got our solution in O(n) !
I will post C code for this later.
No comments:
Post a Comment