High Arrays Question 143 of 224

How do you find the duplicate number in 1..n when exactly one value is repeated and you may not modify the array?

DSA interview set · Speak this in 60–90 seconds · Faridabad & Delhi NCR

01234

Index starts at 0. Scan once for max — O(n).

Treat the array as a functional graph of next = nums[i] and run Floyd cycle detection

Why interviewers care about Arrays:

This is a process

question about Arrays.

Panels listen for order,

trade-offs, and what you would actually do on a DSA project - not buzzwords.

Stay structured

Name the idea, why it exists, then one short example.

Close cleanly

End with when you use it and one common pitfall.

Before you speak the answer, walk the interviewer through these steps:

1
Treat the array as
a functional graph of next = nums[i] and run Floyd cycle detection
2
the cycle entrance is
the duplicate.
3
Time is O(n) and
space is O(1).
4
Binary search on count
of values <= mid is also O(n log n) time and O(1) space if they dislike Floyd.
5
Common mistake
What juniors usually get wrong.
6
Close
When you pick this over the alternative.

Here's a short line you can speak, broken into clear beats:

Say this line

“Time is O(n) and space is O(1).”

Break into beats

TimeisOnandspace

Speaking order

2987408337471632900

Note: Adapt this scaffold to your own project — keep it under 60–90 seconds.

Treat the array as a functional graph of next = nums[i] and run Floyd cycle detection the cycle entrance is the duplicate.