287. Find the Duplicate Number — LeetCode(Python)

I got you!

Problem:

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.

Example 1:

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

Example 2:

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

Constraints:

• 1 <= n <= 105
• nums.length == n + 1
• 1 <= nums[i] <= n
• All the integers in nums appear only once except for precisely one integer which appears two or more times.

Follow up:

• How can we prove that at least one duplicate number must exist in nums?
• Can you solve the problem in linear runtime complexity?

Solution:

slow, fast = 0, 0
while True:
    slow = nums[slow]
    fast = nums[nums[fast]]
    if slow == fast:
        break
            
slow2 = 0
while True:
    slow = nums[slow]
    slow2 = nums[slow2]
    if slow == slow2:
        return slow

Explanation —

This is a version of Linked List Cycle on LeetCode.

There are two steps we need to take to solve this problem:

• Identify that this is a Linked List problem
• Apply Floyd’s Tortoise and Hare algorithm

Step 1:

First of all, where does the cycle come from? Let’s use the function f(x) = nums[x] to construct the sequence: x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ....

Each new element in the sequence is an element in nums at the index of the previous element.

If one starts from x = nums[0], such a sequence will produce a linked list with a cycle.

The cycle appears because nums contains duplicates. The duplicate node is a cycle entrance.

The above lines have been borrowed from LeetCode’s official solution and are very easy to understand.

Step 2:

After identifying that this is a linked list problem, we now have to apply Floyd’s algorithm on it.

We use a two-pointer approach. We have a fast and a slow pointer, where the fast pointer is twice as fast as the slow pointer.

Both pointers start at the head of the linked list and intersect for the first time inside the cycle.

Now, we need to know that the distance from the head of the linked list and the intersection point to the start of the cycle is the same.

We use this concept to now slow down our fast pointer and find where it now meets our slow pointer.

The new meeting point is the starting point of the linked list cycle.

Time and Space Complexity —

Our solution takes linear time and constant extra space.

Thus, if n is the length of the array nums,

Time Complexity: O(n)

Space Complexity: O(1)

Please refer to NeetCode’s solution video to this problem: https://www.youtube.com/watch?v=wjYnzkAhcNk

Hope this helps!

Feel free to ask any related questions in the comment section or the links provided down below.

I don’t have friends:

Let’s be friends!

Connect with me on:

LinkedIn

GitHub

Instagram (I know. Very professional)

Jai Shri Ram 🙏