287. Find the Duplicate Number 🚀
Tags: javascript, leetcode, tutorial, beginners
Published: 2022-09-29 13:49:56

***
### Solution Developed In:
![JavaScript](https://img.shields.io/badge/javascript-%23323330.svg?style=for-the-badge&logo=javascript&logoColor=%23F7DF1E)

## The Question
For this article we will be covering Leetcode's '[287. Find the Duplicate Number](https://leetcode.com/problems/find-the-duplicate-number/)' question. An question that you'll never solve in constant space without Google (Or knowing [floyd's turtle and hare](https://en.wikipedia.org/wiki/Cycle_detection))

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](https://leetcode.com/problems/linked-list-cycle/) or [142. Linked List Cycle](https://leetcode.com/problems/linked-list-cycle-ii/). 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](https://en.wikipedia.org/wiki/Cycle_detection) 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](https://www.quora.com/How-do-I-prove-that-the-tortoise-and-hare-in-Floyd-s-cycle-detection-algorithm-definitely-meet-if-a-cycle-exists-How-do-I-determine-the-starting-point-of-a-cycle-in-a-linked-list);
![JavaScript](https://qph.cf2.quoracdn.net/main-qimg-ec43b76b3b337adb305f7a58e7874845);

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: 
[![LeetCode](https://img.shields.io/badge/LeetCode-000000?style=for-the-badge&logo=LeetCode&logoColor=#d16c06)](https://leetcode.com/submissions/detail/809807907/)


***

# 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
};
```