Here is solutions for Find the Duplicate Number.

1. Understand the Problem

• You’re given an integer array nums of length n + 1.
• Each element is in the range [1, n].
• There is exactly one repeated number, but it may be repeated more than once.

Your task: Return the duplicate number.

📌 Example: Input: nums = [1, 3, 4, 2, 2] → Output: 2

2. Clarify Constraints & Questions

1. Can there be more than one duplicate number?

• No, exactly one unique number is duplicated one or more times.

1. Can we modify the input array?

• No, must not modify array (in optimal solution).

1. Do we need constant extra space?

• Optimal solution should use O(1) extra space.

1. Can we use sorting?

• Sorting modifies input; acceptable only if constraints do not forbid modification.

1. What if no duplicate exists?

• Given constraints guarantee only ONE duplicate.

3. Explore Examples

4. Brainstorm 2 - 3 solutions

4.1. Brute force - Time O(N^2), Space O(1)

• Brute force [i, j] in 2 loops.

• Time: O(N^2).

• Space: O(1)

4.2. Sorting - Time O(NlogN), Space O(1)

• Sorting and find adjacent elements.

• Time: O(NlogN)

• Space: O(1)

4.3. Use Hash Set - Time O(N), Space O(N)

• Keep the hash set to find keys with O(1)

• Time: O(N)

• Space: O(N)

4.4. Fast and Slow - Floyd’s Cycle Detection (Tortoise & Hare) - Time O(N), Space O(1)

• Key ideas:

nums = [1,3,4,2,2]

0 → 1
1 → 3
3 → 2
2 → 4
4 → 2 ← cycle (duplicate: 2)

• Why fast = nums[nums[fast]], slow = nums[slow], because fast move 2 steps, twice than slow.

fast = nums[fast]         # 1st jump
fast = nums[fast]         # 2nd jump

Notes:

• Idea: Still fast will meet slow pointer if start in the same start.

• Step 1: fast and slow meet each other => Only confirm it meet inside the cycle.

• Step 2: Start to actually find the duplicate value.

4.5. Binary search - Time O(NlogN), Space O(1)

• Key idea:

  • If we have more than mid numbers in range [1, mid], some value must be duplicated there.

• Time: O(NlogN)

• Space: O(1)

4.6. Bit Manipulation

1. Key Idea:

You have numbers from 1 to n-1, and one number duplicated.

• If all numbers were unique, we could predict how many times each bit should appear.

• But because one number appears twice, bits set in the duplicate appear more times than expected.

1. Count bits in two groups

• The different bits from left to right is about the duplicate value from 32 bits [0 -> 31].

👉 If x > y → that bit belongs to the duplicate.

4.7. Negative Marking

• Marking the nums[i] to negative => To check if negative means it have existed.

• Time: O(N)

• Space: O(1)

5. Implement solutions

5.1. Sorting - Time O(NlogN), Space O(1)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        nums.sort()
        for i in range(len(nums) - 1):
            if nums[i] == nums[i + 1]:
                return nums[i]
        return -1

• Time: O(NlogN)

• Space: O(1)

5.2. Hash Set - Time O(N), Space O(N)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = set()
        for num in nums:
            if num in seen:
                return num
            seen.add(num)
        return -1

• Time: O(N)

• Space: O(N)

5.3. Array Counting - Time O(N), Space O(N)

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        seen = [0] * len(nums)
        for num in nums:
            if seen[num - 1]:
                return num
            seen[num - 1] = 1
        return -1

• Time: O(N)

• Space: O(N)

5.4. Negative marking

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        for num in nums :
            idx = abs(num) - 1
            if nums[idx] < 0 :
                return abs(num)
            nums[idx] *= -1
        return -1

• Time: O(N)

• Space: O(1)

5.5. Binary Search

• Key idea:

  • If we have more than mid numbers in range [1, mid], some value must be duplicated there.

  => Mid is value not only index.

  class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        low, high = 1, n - 1
        while low < high:
            mid = low + (high - low) // 2
            lessOrEqual = sum(1 for num in nums if num <= mid)
  
            if lessOrEqual <= mid:
                low = mid + 1
            else:
                high = mid
  
        return low
  

• Time: O(NlogN)

• Space: O(1)

5.6. Bit manipulation

• The different bits from left to right is about the duplicate value from 32 bits [0 -> 31].

👉 If x > y → that bit belongs to the duplicate.

=> Only work for 1 duplicate value

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        n = len(nums)
        res = 0
        for b in range(32):
            x = y = 0
            mask = 1 << b
            for num in nums:
                if num & mask:
                    x += 1

            for num in range(1, n):
                if num & mask:
                    y += 1

            if x > y:
                res |= mask
        return res

• Time: O(32 * N)

• Space: O(1)

5.7. Fast And Slow Pointers - Tortoise and Hare

Key idea:

• A: start -> duplicate value

• B: duplicate value -> meeting point

• C: meeting point -> finish the loop.

• Velocity: slow = T, fast = 2T.

-> fast and slow meet at meeting point

-> (A + 2B + C) / 2T = (A + B) / T

=> 2A = A + C => A = C

=> slow move A steps, slow1 move C step and meet the duplicate value

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow, fast = 0, 0

        # Meeting point
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break

        # Duplicate value
        slow2 = 0
        while True:
            slow = nums[slow]
            slow2 = nums[slow2]
            if slow == slow2:
                return slow

• Time: O(N)

• Space: O(1)

6. Dry run examples

0 → 1 → 3 → 2 → 4 → 2 → (cycle starts here)

6.1. Phase 1: Detect Cycle (Fast = 2 steps, Slow = 1 step)

6.2. Phase 2: Find Starting Point of Cycle (Duplicate)