287. Find the Duplicate Number 🚀

---

Solution Developed In:

The Question

For this article we will be covering Leetcode's '287. Find the Duplicate Number' question. An question that you'll never solve in constant space without Google (Or knowing floyd's turtle and hare)

Question:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.

Input: nums = [1,3,4,2,2]
Output: 2

Explaining The Question

This Question is rated Medium. Which is I would say is in-accurate, especially if you've never solved 141. Linked List Cycle or 142. Linked List Cycle. I'd almost say this was impossible to solve without knowing how to solve both of these problems, unless you're Robert W. Floyd himself.

So how do we really solve this question? floyd's turtle and hare is the only way to solve this question to my understanding.
Alright, so you know we can solve it with this Turtle & Hare approach. But what the hell is it you ask?

Floyds Turtle & Hare is an algorithm designed to find the node that loops back upon. Meaning, it detects cycles in a list. Normally you would do this in a Linked List, but this time we have a Linked List disguised as an Array. Where nums[i] represents the next node.

How does it work?
Well the math behind that is complicated, see for yourself: Proof;
;

Basically, where we move one pointer 1 node at a time (slow) and another a double the speed (fast), our fast will eventually lap around and land on slow. Which mean's a loop has occurred because they shouldn't be able to meet due to their speed difference. So we move our fast pointer back to the start and go 1 node at a time until the pointer meet again. It just so happens when they meet again, they will always meet on the looping node.

The code to achieve this is painfully simple.

---

Big O Notation:

• Time Complexity: O(n) | Where n is the length of the list we're traversing.
• Space Complexity: O(1) | We don't use extra space.

Leetcode Results:

See Submission Link:

---

The Solution

var findDuplicate = function(nums) {
    let slow = 0;
    let fast = 0;

    do {
        slow = nums[slow];
        fast = nums[nums[fast]];
    } while (slow != fast);

    fast = 0;

    do {
        slow = nums[slow];
        fast = nums[fast];
    } while (slow != fast);

    return slow
};

Comments

[GIRIPRASTH.D]

Thanks, I learned a new concept today .