15% off all plans & roadmaps Use code
See plansFind All Duplicates in an Array
- LeetCode 442
- Medium
- Array/Matrix Manipulation Patterns
- Array - Cyclic Sort
Updated
TL;DR: Return every value that appears twice, using O(n) time and O(1) extra space. The winning idea is cyclic sort: move each value to index value minus 1, then read the slots that hold the wrong value.
Problem
Given an integer array nums of length n, where every integer is in the range [1, n] and each integer appears at most twice, return an array of all the integers that appear twice.
You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, not counting the space needed for the output.
Example 1
Input: nums = [4,3,2,7,8,2,3,1] Output: [2,3]
Example 2
Input: nums = [1,1,2] Output: [1]
Example 3
Input: nums = [1] Output: []
Constraints
n == nums.length1 <= n <= 10^51 <= nums[i] <= n- Each element in
numsappears once or twice.
Constraints that matter
- n up to 10^5 rules out the nested-loop brute force, which does about n^2 / 2 comparisons.
- Values are between 1 and n, so each value has a matching index (value minus 1). That mapping is what makes O(n) possible.
- Constant auxiliary space rules out a hash set or a seen array, so the array itself must carry the state.
- Each value appears at most twice, so a slot can hold at most one displaced duplicate per value. That keeps the final scan simple.
Hints
Hint 1
The values run from 1 to n, and the array has exactly n slots.
Hint 2
The naive check compares every pair.
Solution
Intuition
The values run from 1 to n, and the array has exactly n slots. Each value v has one home, index v minus 1, so the array can act as its own lookup table. You do not need a hash set if each value can be placed where it belongs.
Picture a row of n numbered seats, where ticket v belongs in seat v. Each swap seats one more ticket correctly, and a second ticket with the same number is left standing in a wrong seat.
This points to the Cyclic Sort pattern. Recognise it when the values fit a range tied to the array length, such as 1 to n or 0 to n minus 1, and the question asks which values are repeated or missing. Cyclic sort moves each value to its home, and whatever sits in a wrong slot afterwards is your answer.
It works because a value that lands in its home never moves again. Each swap fixes one slot, so the total number of swaps stays below n. A second copy of a value finds its home already taken, so it stays in a wrong slot, and that slot shows where the duplicate is.
Worked example
Input: nums = [4, 3, 2, 7, 8, 2, 3, 1] Output: [2, 3] Explanation: The value 2 sits at positions 2 and 5 (0-based), and the value 3 sits at positions 1 and 6. Every other value appears once. The result lists each repeated value once, and the problem accepts the two values in any order.
Approach 1: Brute force, compare every earlier position
The naive check compares every pair. For each position i, scan every earlier position j. If nums[j] equals nums[i], the value at i is a second copy, so record it and stop scanning for that i.
Each duplicate is recorded once, at its second occurrence, because no value appears more than twice. The method uses only a few indices of extra memory. The cost is the nested scan over all earlier positions.
Steps
- Create an empty result list.
- For each index i from 0 to n - 1, scan every index j from 0 to i - 1.
- If nums[j] equals nums[i], append nums[i] to the result and stop the inner scan.
- Return the result.
Dry run
Take nums = [4, 3, 2, 7, 8, 2, 3, 1]. Positions 0 to 4 find no earlier match. At i = 5, nums[2] is 2, so record 2. At i = 6, nums[1] is 3, so record 3, and i = 7 finds no match, leaving [2, 3].
Complexity
| Time | O(n^2) |
|---|---|
| Space | O(1) extra |
Let n be the array length. On the pass for index i, the inner loop runs i times, so the total is 0 + 1 + ... + (n - 1), which equals n(n - 1) / 2 comparisons. That is O(n^2). The only extra state is two indices and the output list, so auxiliary space is O(1).
PythonTested in our runner
from typing import List, Optional
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
res = []
n = len(nums)
for i in range(n):
# Look for an earlier copy of nums[i]
for j in range(i):
if nums[j] == nums[i]:
res.append(nums[i])
break
return resApproach 2: Sort, then scan neighbours
What's slow: the brute force repeats a search for an earlier twin at every position, and most of those comparisons find nothing. Sorting fixes that by placing equal values next to each other.
The insight that fixes it: after a sort, one neighbour check per position finds every twin. The sort costs O(n log n), which beats n squared but still misses the O(n) bound the problem asks for.
Steps
- Sort nums in ascending order.
- Set i to 1.
- If nums[i] equals nums[i - 1], append nums[i] to the result.
- Increase i and repeat until the end of the array.
- Return the result.
Dry run
Sorting the example gives [1, 2, 2, 3, 3, 4, 7, 8]. Position 2 holds 2, equal to position 1, so record 2. Position 4 holds 3, equal to position 3, so record 3. Every other position differs from its left neighbour, so the result is [2, 3].
Complexity
| Time | O(n log n) |
|---|---|
| Space | O(1) extra with an in-place sort |
Let n be the array length. A comparison sort does O(n log n) comparisons, and that cost dominates. The neighbour scan compares each position with the one before it, which is n - 1 steps and O(n) work. Space is O(1) for the scan, but the sort's own internal buffer depends on the language, so an in-place sort is needed for that bound.
PythonTested in our runner
from typing import List, Optional
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
nums.sort() # equal values end up next to each other
res = []
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
res.append(nums[i])
return resThe Array - Cyclic Sort infographic is part of Pro
A one-page visual of the pattern: when it applies, the steps and the invariant to keep.
Unlock the infographicSolution pattern
Array - Cyclic Sort
Approach 3: Cyclic sort, then scan for wrong slotsOptimalArray - Cyclic Sort
What's slow: sorting orders every value, but the question only asks which values are out of place. Work on all n values is more than needed.
The insight that fixes it: each value in the range 1 to n has a home slot, so you can move values home with swaps. Each swap settles one slot for good, so there are at most n swaps. Afterwards, any slot whose value differs from its index plus one holds a duplicate, and one scan reads them off.
Steps
- Set i to 0.
- While i is less than n, let c be nums[i] - 1, the home index of nums[i].
- If nums[i] differs from nums[c], swap the two values and do not move i, because the new value at i still needs checking.
- If nums[i] equals nums[c], increase i. The value is home, or its home already holds an equal copy.
- Scan j from 0 to n - 1 and collect nums[j] wherever nums[j] is not j + 1.
- Return the collected values.
Dry run
Columns: i is the scan pointer, c is the home index of nums[i], and the last column is the array after the step.
| Step | i | c | Action | Array after step |
|---|---|---|---|---|
| 1 | 0 | 3 | 4 vs nums[3]=7, differ, swap | [7,3,2,4,8,2,3,1] |
| 2 | 0 | 6 | 7 vs nums[6]=3, differ, swap | [3,3,2,4,8,2,7,1] |
| 3 | 0 | 2 | 3 vs nums[2]=2, differ, swap | [2,3,3,4,8,2,7,1] |
| 4 | 0 | 1 | 2 vs nums[1]=3, differ, swap | [3,2,3,4,8,2,7,1] |
| 5 | 0 | 2 | 3 vs nums[2]=3, equal, i moves to 1 | [3,2,3,4,8,2,7,1] |
| 6 | 1 | 1 | 2 vs nums[1]=2, equal, i moves to 2 | [3,2,3,4,8,2,7,1] |
| 7 | 2 | 2 | 3 vs nums[2]=3, equal, i moves to 3 | [3,2,3,4,8,2,7,1] |
| 8 | 3 | 3 | 4 vs nums[3]=4, equal, i moves to 4 | [3,2,3,4,8,2,7,1] |
| 9 | 4 | 7 | 8 vs nums[7]=1, differ, swap | [3,2,3,4,1,2,7,8] |
| 10 | 4 | 0 | 1 vs nums[0]=3, differ, swap | [1,2,3,4,3,2,7,8] |
| 11 | 4 | 2 | 3 vs nums[2]=3, equal, i moves to 5 | [1,2,3,4,3,2,7,8] |
| 12 | 5 | 1 | 2 vs nums[1]=2, equal, i moves to 6 | [1,2,3,4,3,2,7,8] |
| 13 | 6 | 6 | 7 vs nums[6]=7, equal, i moves to 7 | [1,2,3,4,3,2,7,8] |
| 14 | 7 | 7 | 8 vs nums[7]=8, equal, i moves to 8 and the loop stops | [1,2,3,4,3,2,7,8] |
The final scan checks each slot. Index 4 holds 3, not 5, and index 5 holds 2, not 6, so the scan returns [3, 2]. The example lists [2, 3], and the problem accepts any order.
Complexity
| Time | O(n) |
|---|---|
| Space | O(1) extra |
Let n be the array length. Each swap settles one slot for good, so there are at most n swaps, and i advances at most n times. The final scan adds n more steps, so total work is O(n). Only the indices and one temporary value are extra, so space is O(1) apart from the output.
PythonTested in our runner
from typing import List, Optional
class Solution:
def findDuplicates(self, nums: List[int]) -> List[int]:
n = len(nums)
i = 0
while i < n:
c = nums[i] - 1 # home index of nums[i]
if nums[i] != nums[c]:
nums[i], nums[c] = nums[c], nums[i]
else:
i += 1
res = []
for j in range(n):
if nums[j] != j + 1:
res.append(nums[j])
return resCommon mistakes
- Advancing
iafter every swap, as inswap(nums[i], nums[c]); i++. The value swapped into positioniis never checked, so misplaced values stay where they are. Fix: moveionly whennums[i]equalsnums[c]. - Swapping without the check
nums[i] != nums[c]. With two copies of 3, the swap changes nothing and the loop repeats forever. Fix: test equality before every swap. - Indexing
nums[nums[i]]instead ofnums[nums[i] - 1]. Value n then reads past the end, and other values read the wrong slot. Fix: subtract one to get the home index. - Reversing the final test, as in
if nums[j] == j + 1. That returns the values that are already in place. Fix: testnums[j] != j + 1. - Appending
j + 1instead ofnums[j]to the result. The output must hold the duplicate values, andj + 1is the missing value. Fix: append the value stored at the wrong slot. - Returning a List from the Java method. The starter signature returns
int[], so a List return fails to compile. Fix: count the wrong slots, allocate an array, and fill it.
Edge cases
- nums = [1] returns []. The only value is already at its home, so no swap runs and the scan finds nothing.
- nums = [1, 1] returns [1]. Position 1 holds a second 1, and the final scan finds it at index 1.
- nums = [2, 2] returns [2]. Position 0 holds 2, and its home index 1 already holds an equal 2, so the loop moves on. The final scan finds the 2 at index 0 and returns [2].
- nums = [1, 1, 2, 2] returns two values, [1, 2] in index order. Values 3 and 4 are missing, and that is valid input.
- nums = [1, 2, 3, 4, 5] returns []. Every value is in its home, so the loop makes no swaps.
- A permutation of 1 to 10^5 with no duplicates returns []. The cyclic sort still finishes in linear time, because each slot is settled at most once.
Follow-ups interviewers ask
Follow-ups are part of Pro
The questions interviewers ask after you solve Find All Duplicates in an Array, with how to answer them.
Unlock the follow-upsFind All Duplicates in an Array FAQ
What is the time complexity of Find All Duplicates in an Array?
The cyclic sort solution runs in O(n) time, where n is the array length. Each swap settles one slot, so there are at most n swaps, and the final scan adds n more steps. The brute force takes O(n^2), and sorting first takes O(n log n).
Why use cyclic sort for Find All Duplicates in an Array?
Each value from 1 to n has exactly one home index, so the array can act as its own lookup table. Moving values home with swaps costs O(n) in total and leaves each duplicate in a wrong slot. That meets the O(1) extra space limit, which a hash set cannot.
Can Find All Duplicates in an Array be solved in O(1) extra space?
Yes. The cyclic sort solution uses only a few indices and one temporary value, and the output list does not count toward the limit. It modifies the input array while it runs, which is the trade that makes the constant space bound possible.
When should you use cyclic sort?
Use it when the values fit a range tied to the array length, such as 1 to n or 0 to n minus 1, and the question asks for repeated or missing values in O(n) time. Problems like Find All Numbers Disappeared in an Array and Missing Number follow the same pattern.
Does the order of the result matter?
No. The problem accepts the duplicates in any order. The cyclic sort version returns them in index order, which can differ from ascending value order, while the brute force returns them in the order of each second occurrence.
Why does JavaScript need a comparator when sorting this array?
The default JavaScript sort compares values as strings, so 10 comes before 2. Pass a comparator such as (a, b) => a - b to sort numbers numerically. The duplicate check still works with the default sort, but the order is wrong for other uses.
Asked at
See which companies ask this — Pro
Related problems
- Find the Duplicate Number · same technique: Array - Cyclic Sort
- First Missing Positive · same technique: Array - Cyclic Sort
- Missing Number · same technique: Array - Cyclic Sort
- Find All Numbers Disappeared in an Array · same technique: Array - Cyclic Sort
- Longest Substring Without Repeating Characters · same pattern: Array/Matrix Manipulation Patterns
- Group Anagrams · same pattern: Array/Matrix Manipulation Patterns
- Longest Consecutive Sequence · same pattern: Array/Matrix Manipulation Patterns
- Top K Frequent Elements · same pattern: Array/Matrix Manipulation Patterns
- Task Scheduler · same pattern: Array/Matrix Manipulation Patterns
- Product of Array Except Self · same pattern: Array/Matrix Manipulation Patterns