⚡Flashcard Drill➔
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

  1. Treat the array as a functional graph: index i points to nums[i]. Since some value repeats, two indices point to the same node, creating a cycle.
  2. The duplicate value is exactly the entrance of the cycle.
  3. 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.
  4. 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.
🎯 Drill This Card Now➔

🧩 Related Linked List Problems