Slow fast pointer solution with key ideas explained.


  • 0
    V

    There are 3 key ideas here :

    (a) Slow and fast definitely meet (because they enter a cycle).
    => Well, if two pointers are running in a circle at speeds x and 2 * x, then they would definitely meet.
    Let us say the slow pointer and fast pointer are at distance z in the circle, then, since the distance b/w then is decreased by 1 at every move, they would meet after 2 * z moves.

    (b) Entry point to the cycle is the duplicate number.
    => let us say index a, b contain the duplicate number say (x), then nums[a] = x, nums[b] = x. let us say nums[x] = y. So, after reaching x, the pointer trverses to y and follows some path p2 and reaches b (note that p2 does not contain any index which has visited before, why? because if it does then that index is repepeated twice and there are more than one duplicate number in the array) and follows b -> x total path : start->p1->a->x- >p2->b->x->p2->b->x.... If we notice carefully the repetition starts at index x and the pattern continues. therefore duplicate number is the entry point to the circle.

    (c) The meeting point of slow and fast pointers is excatly at the same distance from start to enter point.
    => There is an excellent proof already provided, I will repeat it though.
    let the distance travelled by slow ointer be s, the the fast pointer would have travelled 2s distance.
    now, 2s = s + n * c (where c is the cycle length)
    s = n * c -> (1)
    next, let the distance from starting point to entry of the cycle be d and the distance from entry point to the meeting point be a
    then d + a = s = n * c
    d = (n - 1) * c + (c - a);
    where (c - a) is the distance from meeting point to the entry of the circle. This prooves that when the pointer starts at the start of the array and travels (n-1)
    c + (c-a) distance, it would reach the entry of the cycle as will the pointer with in the loop.

    This proof mostly is a copy of one of the proofs i have seen on leetcode.

    public class Solution {
    public int findDuplicate(int[] nums) {
            if (nums.length  > 0) {
                int slow = nums[0];
                int fast = nums[nums[0]];
                
                while (slow != fast) {
                    slow = nums[slow];
                    fast = nums[nums[fast]];
                }
                
                fast = 0;
                while(slow != fast) {
                    fast = nums[fast];
                    slow = nums[slow];
                }
                
                return slow;
            }
            
            return -1;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.