Given an array of integers nums containing 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 using only constant extra space.
Example 1:
Input: nums = [1,3,4,2,2] Output: 2
Example 2:
Input: nums = [3,1,3,4,2] Output: 3
Example 3:
Input: nums = [3,3,3,3,3] Output: 3
Constraints:
1 <= n <= 105nums.length == n + 11 <= nums[i] <= nnums appear only once except for precisely one integer which appears two or more times.
Follow up:
nums?This approach uses cycle detection to find the duplicate number using two pointers. Imagine the numbers in the array form a linked list, where the value at each index points to the next index. When there is a duplicate, a cycle will be formed. The first step is to find the intersection point of the cycle using a slow and fast pointer. Once they meet, use two pointers to find the entrance of the cycle, which will be the duplicate number. This method doesn't modify the array and uses O(1) space.
This C solution implements the cycle detection algorithm. Two pointers, slow and fast, iterate through the array. First they meet in the cycle; then, by resetting one and moving both pointers step by step, they meet at the duplicate number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n), where n is the size of the array. Space Complexity: O(1), since we use a constant amount of extra space.
This approach leverages a binary search technique on the range of possible values of the duplicate number. For each midpoint in this range, count how many numbers are less than or equal to it. If the count is greater than the midpoint, the duplicate must be in the lower range; otherwise, it is in the upper range. Binary search is applied until the duplicate is found. This doesn't require additional space and doesn't alter the input array.
This C solution uses binary search on the range of possible numbers, counting numbers less than or equal to the midpoint, and then adjusting the binary search boundaries accordingly, eventually discovering the duplicate number.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n). Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Approach 1: Floyd's Tortoise and Hare (Cycle Detection) | Time Complexity: O(n), where n is the size of the array. Space Complexity: O(1), since we use a constant amount of extra space. |
| Approach 2: Binary Search on Result | Time Complexity: O(n log n). Space Complexity: O(1). |
Contains Duplicate - Leetcode 217 - Python • NeetCode • 770,501 views views
Watch 9 more video solutions →Practice Find the Duplicate Number with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor