Find the Duplicate Number

Cyclic Sort

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 duplicate number in nums, return this duplicate number.

For example:

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

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

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

Solution

def find_duplicate(nums):
    i = 0
    while i < len(nums):
        if nums[i] != i+1:
            j = nums[i] - 1
            if nums[i] != nums[j]:
                nums[i], nums[j] = nums[j], nums[i]
            else:
                return nums[i]
        else:
            i+=1
    return -1
    
    
#Following cyclic sort, we will try to place each 
number on its correct index.
#Since there is only one duplicate, if while swapping
#the number with its index both the numbers being 
#swapped are same, we have found our duplicate!

#Time: O(n)
#Space: O(1)