DevOps NetworkDevOpsNetwork
Join Free
DSA patterns

Find All Duplicates in an Array

mediumArrays and hashing

Problem statement

You are given a list nums of length n. Every value is between 1 and n, and each value appears either once or twice. Return every value that appears twice, in any order.

The target is O(n) time using only constant extra space (the output list does not count).

Examples

Example 1

Input: nums = [5, 2, 5, 1, 3, 2]

Output: [5, 2]

Explanation: n is 6. Both 5 and 2 appear twice. Any order is accepted.

Example 2

Input: nums = [1, 2, 3]

Output: []

Explanation: Every value appears once.

Hints

Approach

Use the list itself as the "seen" set. Because every value v is between 1 and n, index v - 1 always exists. Mark v as seen by making the number at that index negative.

  1. For each element, take its absolute value v (it may already have been negated by an earlier mark).
  2. Look at nums[v - 1].
  3. If it is already negative, v was seen before, so add v to the result.
  4. Otherwise negate it to mark v as seen.

The signs carry the extra information, so no other memory is needed. This changes the input; if the caller needs it back, take abs of every element at the end.

ComplexityTime O(n)Space O(1) extra
Python
class Solution:
def findDuplicates(self, nums: list[int]) -> list[int]:
result = []
for x in nums:
v = abs(x)
if nums[v - 1] < 0:
result.append(v)
else:
nums[v - 1] = -nums[v - 1]
return result

Follow-up questions

  • Return the values from 1 to n that never appear, using the same marking trick.
  • Find the single repeated value without modifying the list at all.

Frequently asked questions

An earlier step may have negated this position to mark some other value. The original value is still there, just with a flipped sign, so abs recovers it before you use it as an index.

Not directly. The third occurrence would see a negative mark and be reported again. You would need to report only on the first repeat, for example by skipping values already in the result, or by using a different marking scheme.

Ask first. Many interviewers allow it for this problem because the constant-space requirement is the point. In production code you would usually restore the values or work on a copy.