Solution: Find The Duplicate Number

Let's solve the Find The Duplicate Number problem using the the Fast and Slow pattern.

Statement

Given an array of positive numbers, nums, such that the values lie in the range [1,n][1, n], inclusive, and that there are n+1n+1 numbers in the array, find and return the duplicate number present in nums. There is only one repeated number in nums.

Note: You cannot modify the given array nums. You have to solve the problem using only constant extra space.

Constraints:

  • 1n1031 \leq n \leq 10^3
  • nums.length =n+1= n + 1
  • 11 \leq nums[i] n\leq n
  • All the integers in nums are unique except for one integer that will appear more than once.

Solution

We solve this problem using fast and slow pointers technique, without modifying the nums array and using only constant extra space.

For this problem, the duplicate number will create a cycle in the nums array. The cycle in the nums array helps identify the duplicate number.

To find the cycle, we’ll move in the nums array using the f(x)=nums[x]f(x) = nums[x] function, where xx is the index of the array. This function constructs the following sequence to move:

x, nums[x], nums[nums[x]], nums[nums[nums[x]]], ...x, \space nums[x], \space nums[nums[x]], \space nums[nums[nums[x]]], \space ...

In the sequence above, every new element is an element in nums present at the index of the previous element.

Let’s say we have an array, [2, 3, 1, 3][2, \space 3,\space 1,\space 3]. We’ll start with x=nums[0]x=nums[0], which is 22, present at the 0th0^{th} index of the array and then move to nums[x]nums[x], which is 11, present at the 2nd2^{nd} index. Since we found 11 at the 2nd2^{nd} index, we’ll move to the 1st1^{st} index, and so on. This example shows that if we’re given an array of length n+1n+1, with values in the range [1, n][1,\space n], we can use this traversal technique to visit all the locations in the array.

The following example illustrates this traversal:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.