How do you find a duplicate in an array? | Interview Question

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

**Target Audience:** Beginners preparing for coding interviews — you know Python lists, loops and sets; nothing else assumed. **Difficulty:** Easy (the general version); the O(1)-space Floyd variant is often graded Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact words an interviewer expects. Every output shown was produced by running the code with `python3` (3.13); nothing is typed in by hand. ## 1. Why This Even Matters — A Story First A theatre cloakroom has hooks numbered 1 to 4. At the end of the night, the attendant finds **five** coat tickets in the box, each with a hook number written on it. Five tickets, four hooks: at least two tickets **must** name the same hook. Which hook was given out twice? - The simplest method: read the tickets one by one and keep a checklist of hook numbers already seen. The first number already ticked is the answer. Fast, bu

The problem

Question presented to candidate: "Given a list of integers, find a number that appears more than once. First solve it in general, then for the classic version — n + 1 numbers, each between 1 and n, without modifying the list and with O(1) extra space. Please code it in Python."

What a strong answer should cover:

Asking about the constraints first: value range, whether the list may be modified, the memory budget, one or several repeated values.
The general answer: scan with a set, return the first value already in it — O(n) time, O(n) space.
The alternatives: sort and compare neighbours (O(n log n)), index negation (O(n), O(1) space, modifies the list), and Floyd's cycle detection on i → nums[i] (O(n), O(1) space, read-only), with why the pigeonhole principle guarantees a duplicate.
Why Floyd works: two indices point to the duplicate, so it is the entrance of the cycle.
Python specifics: x in seen on a set is O(1) average but on a list is O(n); sorted() returns a copy while list.sort() mutates; len(set(nums)) != len(nums) for a yes/no; negative indices are valid in Python, so some index bugs are silent.

Clarifying questions expected:

What is the value range? May I modify the list? How much extra space?

Code / implementation expected: Yes — a set-based find_duplicate in Python, plus the Floyd version for the 1..n constraint.

arrays
duplicates

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you know Python lists, loops and sets; nothing else assumed. Difficulty: Easy (the general version); the O(1)-space Floyd variant is often graded Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact words an interviewer expects. Every output shown was produced by running the code with python3 (3.13); nothing is typed in by hand.

1. Why This Even Matters — A Story First

A theatre cloakroom has hooks numbered 1 to 4. At the end of the night, the attendant finds five coat tickets in the box, each with a hook number written on it. Five tickets, four hooks: at least two tickets must name the same hook. Which hook was given out twice?

The simplest method: read the tickets one by one and ke

The solution is hidden so you can try first

15 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonHash set (any values) and Floyd cycle detection (values 1..n)

Practice

PythonFour approaches side by side, with a Floyd trace

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.