Find All Duplicates in an Array
Find All Duplicates in an Array: every integer in nums lies in [1, n] and appears once or twice. Return all the values appearing twice, in O(n) time and without extra space.
- n == nums.length
- 1 <= n <= 10⁵
- 1 <= nums[i] <= n
- Each element in nums appears once or twice
Intuition
The constraint that every value lies in [1, n] means each value names a valid index — the array can act as its own hash table. Visiting value v and flipping the sign at index v - 1 marks that value as seen; encountering an already-negative slot proves v has been visited before. The sign bit supplies one bit of storage per element, which is exactly what a seen set needs, so no extra space is required.
When values are bounded by the array length and O(1) space is demanded, the array itself is the intended storage — via sign marking or cyclic swapping. The tell is the value range matching the index range. Missing Number, First Missing Positive, and Find the Duplicate Number all exploit it.
Approach
Before reading on: work out why the constraint 1 <= nums[i] <= n is what makes the array usable as its own hash table. Then decide why abs() is needed when computing the index.
The value range is the whole trick
Values in [1, n] map one-to-one onto indices [0, n-1] via v - 1. That is what turns the input array into usable scratch space: the slot for value v is a fixed, collision-free location. Without that guarantee — if values could exceed n or be negative — the index would be out of range and the technique would not apply at all. Recognising the range constraint as the enabling condition, rather than incidental detail, is the actual insight.
Encoding *seen* in the sign bit
Iterate the array, and for each element take index = abs(num) - 1. The abs is essential because earlier iterations may already have negated this element, and the magnitude still carries the original value. If nums[index] is already negative, then some earlier element also mapped here, so index + 1 appears twice and is recorded. Otherwise negate nums[index] to mark it seen. Each value's presence is stored destructively but reversibly — the magnitudes are untouched, so the original array can be restored by taking absolute values.
Why this beats the obvious alternatives
A hash set solves it in O(n) time but uses O(n) space, violating the follow-up. Sorting gives O(1) extra space but costs O(n log n) and destroys the ordering. The sign-marking approach achieves both bounds at once because it reuses storage the input already occupies. Each value appears at most twice, so each slot is negated at most once and the duplicate is detected on the second visit — one pass, O(n) time, O(1) extra space beyond the output list.
Solution & live demo
Common pitfalls
Indexing without abs
index = num - 1
index = abs(num) - 1
A previous iteration may already have negated this element, making num negative and the index negative or out of range. The magnitude still holds the original value, so abs recovers it.
Using a hash set
seen = set()
for num in nums:
if num in seen:
result.append(num)
seen.add(num)mark the sign at index abs(num) - 1
Correct and O(n) time, but it uses O(n) extra space, which the problem's follow-up explicitly rules out. The sign bit provides the same one-bit-per-value information for free.
Appending nums[index] instead of index + 1
result.append(nums[index])
result.append(index + 1)
By this point nums[index] has been negated, so it holds the negative of some value rather than the duplicate itself. The duplicated value is what the index encodes: index + 1.
Edge cases
Every slot is negated exactly once and an empty list is returned.
Each pair triggers one detection, so n/2 values are returned.
Index 0 is negated then found negative, reporting 1.
One negation, no duplicate, empty result.
abs(num) recovers the original value, so the mapping stays correct.