easyDSA

How do you find a duplicate in an array?

Q: How do you find a duplicate in an array?

**Intuition.** The approach depends on the constraints. The general tool is a **hash set** (O(n) time, O(n) space). But when the values are bounded in 1..n , you can treat the array as a linked list of "value → index" pointers and find the duplicate with **Floyd's cycle detection** in O(1) extra space. hash-set scan: store each value, flag a repeat 1 <rect x="72" y="44" width="48" height="38" rx="5" fill="#22c55e" fi

97 views

Understand the problem

Explain duplicate detection.

arraysduplicates

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Hash set + Floyd (1..n)

Run Playground

def find_duplicate_set(nums):
    seen = set()
    for x in nums:
        if x in seen:
            return x
        seen.add(x)
    return -1

# O(1) space, values in 1..n (read-only):
def find_duplicate_floyd(nums):
    slow = fast = nums[0]
    while True:
        slow = nums[slow]
        fast = nums[nums[fast]]
        if slow == fast:
            break
    slow = nums[0]
    while slow != fast:
        slow = nums[slow]
        fast = nums[fast]
    return slow


# --- demo ---
print(find_duplicate_set([1, 3, 4, 2, 3]))     # 3
print(find_duplicate_floyd([1, 3, 4, 2, 2]))   # 2  (values 1..4)

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you check if a linked list is a palindrome?

How do you find the maximum depth of a binary tree?