Sign in
Skip to solution
easyDSA

How do you find a duplicate in an array?

98 views
01

Understand the problem

Explain duplicate detection.

arraysduplicates
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

A hash set detects duplicates in O(n) time / O(n) space. If values are in 1..n, Floyd's cycle detection on the index-as-pointer graph finds it in O(1) extra space. Sorting then scanning is O(n log n).

Solution ready — 2 min read

Classified // press E to declassify

04

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)
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 25 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track