Fast/Slow Pointers: Find the duplicate number

by Raul Bojalil

HTML

<div class="markdownViewer select-text  markdown-default markdown-table markdown-viewer markdown-viewer-heading" role="none"><h2 class="hover-anchor" id="Statement" data-id="e912159ba4656d694eefa773cabf35b3">Statement<a href="#Statement"><span class="anchor-link">#</span></a></h2>
<p data-id="129e3b9ddeb0dfd138951af309de4fc2">Given an unsorted array of positive numbers, <code>nums</code>, such that the values lie in the range <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mo stretchy="false">[</mo><mn>1</mn><mo separator="true">,</mo><mi>n</mi><mo stretchy="false">]</mo></mrow><annotation encoding="application/x-tex">[1, n]</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:1em;vertical-align:-0.25em;"></span><span class="mopen">[</span><span class="mord">1</span><span class="mpunct">,</span><span class="mspace" style="margin-right:0.1667em;"></span><span class="mord mathnormal">n</span><span class="mclose">]</span></span></span></span>, inclusive, and that there are <span class="katex"><span class="katex-mathml"><math xmlns="http://www.w3.org/1998/Math/MathML"><semantics><mrow><mi>n</mi><mo>+</mo><mn>1</mn></mrow><annotation encoding="application/x-tex">n+1</annotation></semantics></math></span><span class="katex-html" aria-hidden="true"><span class="base"><span class="strut" style="height:0.6667em;vertical-align:-0.0833em;"></span><span class="mord mathnormal">n</span><span class="mspace" style="margin-right:0.2222em;"></span><span class="mbin">+</span><span class="mspace" style="margin-right:0.2222em;"></span></span><span class="base"><span class="strut" style="height:0.6444em;"></span><span class="mord">1</span></span></span></span> numbers in the array, find and return the duplicate number present in <code>nums</code>. There is only one repeated number in <code>nums</code>.</p>
<blockquote...

JavaScript

function findDuplicate(nums) {
    //  Intialize the fast and slow pointers and make them point the first
    //  element of the array
    let fast = nums[0];
    let slow = nums[0];
    // PART #1
    // Traverse in array until the intersection point is found
    while (true) {
        // Move the slow pointer using the nums[slow] flow
        slow = nums[slow];
        // Move the fast pointer two times fast as the slow pointer using the 
        // nums[nums[fast]] flow 
        fast = nums[nums[fast]];
        // Break the loop when slow pointer becomes equal to the fast pointer, i.e., 
        // if the intersection is found
        if (slow == fast) {
            break;
        }
    }
    // PART #2
    // Make the slow pointer point the starting position of an array again, i.e.,
    // start the slow pointer from starting position
    slow = nums[0];
    // Traverse the array until the slow pointer becomes equal to the
    // fast pointer
    while (slow != fast) {
        // Move the slow pointer using the nums[slow] flow
        slow = nums[slow];
        // Move the fast pointer slower than before, i.e., move the fast pointer
        // using the nums[fast] flow
        fast = nums[fast];
    }
    // Return the fast pointer as it points the duplicate number of the array
    return fast
}

// Driver code
function main(){
    let nums = [
        [1, 3, 2, 3, 5, 4], 
        [2, 4, 5, 4, 1, 3], 
        [1, 6, 3, 5, 1, 2, 7, 4], 
        [1, 2, 2, 4, 3], 
        [3, 1, 3, 5, 6, 4, 2]
    ]
    for (let i = 0; i < nums.length; i++) {
    console.log(i + 1 + ".\tnums = ", nums[i]);
    console.log("\tDuplicate number = ", findDuplicate(nums[i]));
    console.log("-".repeat(100));
    }
}

main()