NeetCode #329LC-287MediumLinked ListNC 150NC 250
← Back to All Problems#329 · #287 · Find the Duplicate Number(寻找重复数)
📌 Problem Statement & Constraints
Given an array
nums of n + 1 integers where each value is in [1, n], exactly one value is repeated (possibly more than twice). Find it without modifying the array and using O(1) extra space. Constraints: 1 <= n <= 10^5, 1 <= nums[i] <= n.💡 Core Algorithmic Approaches
- Treat the array as a functional graph: index
ipoints tonums[i]. Since some value repeats, two indices point to the same node, creating a cycle. - The duplicate value is exactly the entrance of the cycle.
- Apply Floyd's algorithm: first find a meeting point of the slow and fast pointers, then reset one pointer to the start and advance both one step at a time until they meet again.
- That second meeting point is the cycle entrance, i.e. the duplicate.
💻 Benchmark Python3 Implementation
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
# phase 1: find a meeting point inside the cycle
slow = fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# phase 2: find the cycle entrance
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): the two phases each traverse at most O(n) steps.
💾 Space Complexity
O(1): two pointers, and the array is not modified.
⚠️ Interview Pitfalls & Follow-ups
- Sorting or using a set: both are O(n) space or O(n log n) time, and sorting modifies the array.
- Negating values to mark seen indices: O(1) space, but it modifies the array, which is forbidden.
- Forgetting phase 2: the first meeting point is inside the cycle, not necessarily its entrance.
- Initialising both pointers at index 0: the array is 1-indexed in value, so starting at
nums[0]is the standard formulation. Starting at 0 also works if the graph is defined consistently, but be careful.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.