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.
Recommended Time and Space Complexity
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)
Binary Search
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)