Find the Duplicate Number

Problem Statement

You are given an array of integers nums containing n + 1 integers. Each integer in nums is in the range [1, n] inclusive.

Every integer appears exactly once, except for one integer which appears two or more times. Return the integer that appears more than once.

Example 1:

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

Example 2:

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

Follow-up: Can you solve the problem without modifying the array nums and using O(1) extra space?

Constraints:

  • 1 <= n <= 10000
  • nums.length == n + 1
  • 1 <= nums[i] <= n

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

You should aim for a solution with O(n) time and O(1) space, where n is the size of the input array.

Hint 1

A naive approach would be to use a hash set, which takes O(1) time to detect duplicates. Although this solution is acceptable, it requires O(n) extra space. Can you think of a better solution that avoids using extra space? Consider that the elements in the given array nums are within the range 1 to len(nums).

Hint 2

We can use the given input array itself as a hash set without creating a new one. This can be achieved by marking the positions (0-indexed) corresponding to the elements that have already been encountered. Can you implement this?

Hint 3

We iterate through the array using index i. For each element, we use its absolute value to find the corresponding index and mark that position as negative: nums[abs(nums[i]) - 1] *= -1. Taking absolute value ensures we work with the original value even if it’s already negated. How can you detect duplicates?

Hint 4

For example, in the array [2, 1, 2, 3], where 2 is repeated, we mark the index corresponding to each element as negative. If we encounter a number whose corresponding position is already negative, it means the number is a duplicate, and we return it.

Solution

Sorting

def find_duplicate(nums: List[int]) -> int:
nums.sort()
for i in range(len(nums) - 1):
if nums[i] == nums[i + 1]:
return nums[i]
return -1

Time complexity: O(n log n) Space complexity: O(1)

Hash Set

def find_duplicate(nums: List[int]) -> int:
seen = set()
for num in nums:
if num in seen:
return num
seen.add(num)
return -1

Time complexity: O(n) Space complexity: O(n)

Array

def find_duplicate(nums: List[int]) -> int:
seen = [0] * len(nums)
for num in nums:
if seen[num - 1]:
return num
seen[num - 1] = 1
return -1

Time complexity: O(n) Space complexity: O(n)

Negative Marking

def find_duplicate(nums: List[int]) -> int:
for num in nums:
idx = abs(num) - 1
if nums[idx] < 0:
return abs(num)
nums[idx] *= -1
return -1

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

def find_duplicate(nums: List[int]) -> int:
n = len(nums)
low, high = 1, n - 1
while low < high:
mid = low + (high - low) // 2
less_or_equal = sum(1 for num in nums if num <= mid)
if less_or_equal <= mid:
low = mid + 1
else:
high = mid
return low

Time complexity: O(n log n) Space complexity: O(1)

Bit Manipulation

def find_duplicate(nums: List[int]) -> int:
n = len(nums)
res = 0
for b in range(32):
x = y = 0
mask = 1 << b
for num in nums:
if num & mask:
x += 1
for num in range(1, n):
if num & mask:
y += 1
if x > y:
res |= mask
return res

Time complexity: O(32 * n) Space complexity: O(1)

Fast And Slow Pointers

def find_duplicate(nums: List[int]) -> int:
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

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