15% off all plans & roadmaps Use code

See plans

Find All Duplicates in an Array

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.length
  • 1 <= n <= 10^5
  • 1 <= nums[i] <= n
  • Each element in nums appears 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.

View on LeetCode

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.

Watch the pattern animation

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

  1. Create an empty result list.
  2. For each index i from 0 to n - 1, scan every index j from 0 to i - 1.
  3. If nums[j] equals nums[i], append nums[i] to the result and stop the inner scan.
  4. 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

TimeO(n^2)
SpaceO(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 res

Approach 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

  1. Sort nums in ascending order.
  2. Set i to 1.
  3. If nums[i] equals nums[i - 1], append nums[i] to the result.
  4. Increase i and repeat until the end of the array.
  5. 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

TimeO(n log n)
SpaceO(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 res

The 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 infographic

Solution pattern

Array - Cyclic Sort

Part of Array/Matrix Manipulation Patterns

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

  1. Set i to 0.
  2. While i is less than n, let c be nums[i] - 1, the home index of nums[i].
  3. 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.
  4. If nums[i] equals nums[c], increase i. The value is home, or its home already holds an equal copy.
  5. Scan j from 0 to n - 1 and collect nums[j] wherever nums[j] is not j + 1.
  6. 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.

StepicActionArray after step
1034 vs nums[3]=7, differ, swap[7,3,2,4,8,2,3,1]
2067 vs nums[6]=3, differ, swap[3,3,2,4,8,2,7,1]
3023 vs nums[2]=2, differ, swap[2,3,3,4,8,2,7,1]
4012 vs nums[1]=3, differ, swap[3,2,3,4,8,2,7,1]
5023 vs nums[2]=3, equal, i moves to 1[3,2,3,4,8,2,7,1]
6112 vs nums[1]=2, equal, i moves to 2[3,2,3,4,8,2,7,1]
7223 vs nums[2]=3, equal, i moves to 3[3,2,3,4,8,2,7,1]
8334 vs nums[3]=4, equal, i moves to 4[3,2,3,4,8,2,7,1]
9478 vs nums[7]=1, differ, swap[3,2,3,4,1,2,7,8]
10401 vs nums[0]=3, differ, swap[1,2,3,4,3,2,7,8]
11423 vs nums[2]=3, equal, i moves to 5[1,2,3,4,3,2,7,8]
12512 vs nums[1]=2, equal, i moves to 6[1,2,3,4,3,2,7,8]
13667 vs nums[6]=7, equal, i moves to 7[1,2,3,4,3,2,7,8]
14778 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

TimeO(n)
SpaceO(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 res

Common mistakes

  • Advancing i after every swap, as in swap(nums[i], nums[c]); i++. The value swapped into position i is never checked, so misplaced values stay where they are. Fix: move i only when nums[i] equals nums[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 of nums[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: test nums[j] != j + 1.
  • Appending j + 1 instead of nums[j] to the result. The output must hold the duplicate values, and j + 1 is 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-ups

Find 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

Practise it