How do you solve Find the Duplicate Number on LeetCode?

Find the Duplicate Number (LeetCode #287) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n) time complexity and O(1) space complexity. Key insight: Using Floyd's Tortoise and Hare algorithm, we can find the duplicate in linear time and constant space. This method uses the properties of linked lists.

What is the time complexity of Find the Duplicate Number?

The optimal solution for Find the Duplicate Number runs in O(n) time and uses O(1) space. The time complexity is O(n) because we traverse the array at most twice. The space complexity is O(1) since we only use a few pointers.

What is the brute force solution for Find the Duplicate Number?

The brute force approach for Find the Duplicate Number is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute-force approach checks every pair of numbers in the array to find duplicates. It's straightforward but inefficient for larger arrays. The optimal Optimal Solution approach improves this to O(n).

What algorithm or data structure is used to solve Find the Duplicate Number?

Find the Duplicate Number uses the following concepts: Array, Two Pointers, Binary Search, Bit Manipulation. The recommended patterns to study are: .

#287

Find the Duplicate Number

Medium

ArrayTwo PointersBinary SearchBit Manipulation

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n)
Space	O(1)	O(1)

💡

Intuition

Time O(n)Space O(1)

Using Floyd's Tortoise and Hare algorithm, we can find the duplicate in linear time and constant space. This method uses the properties of linked lists.

⚙️

Algorithm

3 steps

1Step 1: Initialize two pointers, slow and fast. Both start at the first element.
2Step 2: Move slow by one step and fast by two steps until they meet.
3Step 3: Reset one pointer to the start and move both pointers one step at a time until they meet again. The meeting point is the duplicate.

solution.py13 lines

1def findDuplicate(nums):
2    slow = nums[0]
3    fast = nums[0]
4    while True:
5        slow = nums[slow]
6        fast = nums[nums[fast]]
7        if slow == fast:
8            break
9    slow = nums[0]
10    while slow != fast:
11        slow = nums[slow]
12        fast = nums[fast]
13    return slow

ℹ

Complexity note: The time complexity is O(n) because we traverse the array at most twice. The space complexity is O(1) since we only use a few pointers.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.