Sale: Get 60% Off on all Pro Plans. Buy Now

Find All Duplicates in an Array

Medium Cyclic Sort

Problem

Given an integer array nums of length n where all elements are in the range [1, n], return an array of all the elements that appear twice in this array.

  • n == nums.length
  • 1 ≤ n ≤ 10⁵
  • 1 ≤ nums[i] ≤ n
  • Each element appears once or twice

Example

Input: nums = [4,3,2,7,8,2,3,1]
Output: [2,3]

A naive approach would count frequencies using extra space, but this violates the O(1) space constraint. The algorithm uses the input array itself to track seen numbers by negating the value at the index corresponding to each number. When a number's corresponding index is already negative, it indicates the number has appeared before and is a duplicate. For example, when processing the second '2', the value at index 1 (2 - 1) is already negative, so '2' is appended to the result.

Approach

Straightforward Solution

A brute-force approach uses a hash map or frequency array to count occurrences, which requires O(n) extra space and is not optimal for space-constrained scenarios.

Core Observation

Each number in nums is in the range [1, n], which means each number can be mapped to an index in the array (number - 1). This allows the array itself to be used as a hash-like structure by marking visited indices.

Path to Optimal

Preview

The key insight is to use the sign of the element at the mapped index to indicate whether the number has been seen before. When a number is encountered, the algorithm negates the value at its corresponding index if it is positive…

Full step-by-step walkthrough on Pro →

Optimal Approach

Preview

Iterate through nums, for each number compute index = abs(num) - 1. If nums[index] is positive, negate it to mark as visited…

Full step-by-step walkthrough on Pro →

Want the full reasoning chain?

Unlock the complete walkthrough, line-by-line analysis, and recall drill.

Unlock Pro

Time

O(n)

The algorithm makes a single pass through the array, performing O(1) operations per element.

Space

O(1)

The solution uses the input array itself for marking and only a constant amount of extra space for the result array, which is required by the problem output.

Pattern Spotlight

Cyclic Sort (In-Place Index Marking)

When elements are constrained to a range [1, n], use the array indices as markers by negating or swapping elements to track presence or duplicates without extra space.

Solution

Python
1class Solution:
2 def findDuplicates(self, nums: list[int]) -> list[int]:
3 res = []
4
5 for num in nums:
6 index = abs(num) - 1
7
8 if nums[index] < 0:
9 res.append(abs(num))
10 else:
11 nums[index] *= -1
12
13 return res

Step-by-Step Solution

1

Accumulate Duplicates by Marking Visited Indices via Negation

3res = []
5for num in nums:
6 index = abs(num) - 1
8 if nums[index] < 0:
9 res.append(abs(num))
10 else:
11 nums[index] *= -1
13return res

Objective

To iterate through the array and use the sign of elements at mapped indices to detect duplicates.

Key Insight

By mapping each number to an index (num - 1), the algorithm uses the sign of the element at that index as a flag. Negating the element marks the number as seen. Encountering a negative value at the mapped index means the number has appeared before, so it is a duplicate. This clever in-place marking avoids extra space while preserving O(n) time.

Interview Quick-Check

Core Logic

Use the absolute value of each number to find its mapped index, then check the sign at that index to determine if the number is a duplicate or not.

State & Boundaries

Always use abs(num) to handle previously negated values and ensure correct index mapping.

Common Pitfalls & Bugs

Failing to use abs(num) can cause incorrect index calculations due to negative values, leading to wrong results or index errors.

Complexity

This approach achieves O(n) time and O(1) auxiliary space by modifying the input array in place.

Line Analysis

This solution has 3 Critical lines interviewers watch for.

Line 8 Critical 
if nums[index] < 0:

Check if the value at the mapped index is negative, indicating the number has been seen before.

A negative value at this index signals that the corresponding number has already been encountered, so the current number is a duplicate.

Line 6 Critical 
index = abs(num) - 1

Calculate the index corresponding to the current number by taking its absolute value minus one.

Using abs(num) ensures that previously negated numbers do not affect the index calculation, maintaining correctness in the presence of in-place modifications.

Line 10 Critical 
else:

Otherwise, negate the value at the mapped index to mark the number as seen.

Negating the value at the mapped index flags that the number has been encountered, enabling detection of duplicates on subsequent visits.

Full line-by-line criticality + rationale for all 8 lines available on Pro.

Test Your Understanding

Why does negating the value at the mapped index correctly indicate whether a number has been seen before?

See the answer with Pro.

Don't just read it. Drill it.

Reconstruct Find All Duplicates in an Array from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.

Unlock the Find All Duplicates in an Array drill

or drill a free problem