Given an array of integers
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.
Input: nums = [1,3,4,2,2] Output: 2
Input: nums = [3,1,3,4,2] Output: 3
Input: nums = [1,1] Output: 1
Input: nums = [1,1,2] Output: 1
2 <= n <= 105
nums.length == n + 1
1 <= nums[i] <= n
- All the integers in
numsappear only once except for precisely one integer which appears two or more times.
- How can we prove that at least one duplicate number must exist in
- Can you solve the problem in linear runtime complexity?
Store the number occurrence in a fixed-length array and check which number occurs more than once.
class Solution: def findDuplicate(self, nums: List[int]) -> int: count = [0 for i in range(len(nums) + 1)] for num in nums: count[num] += 1 if count[num] > 1: return num
- Time Complexity: O(N).
- Space Complexity: O(1).
One Thought to “LeetCode 287. Find the Duplicate Number”
The space complexity is not correct because it creates an extra array of size N + 1, so the extra space complexity is O(N) not O(1)