MediumArrayHash Table

Find All Duplicates in an Array

1 approach, code in every language

You are handed an array of length n where every stored value lies between 1 and n. Some values show up exactly twice while the rest show up exactly once. Return every value that appears twice.

The interesting twist is doing this without extra bookkeeping proportional to the input. Because the values themselves are valid indices, the array can double as its own visited-marker: flipping the sign at the slot a value points to records whether that value has been seen before.

Example 1

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

Output: [2,3]

Both 2 and 3 occur twice; every other number occurs once, so only 2 and 3 are reported.

Example 2

Input: nums = [1,1,2]

Output: [1]

Only the value 1 shows up twice.

Constraints

n == nums.length with 1 ≤ n ≤ 10^5
1 ≤ nums[i] ≤ n
Each element of nums appears once or twice

Index Sign-Flip Marker

Use each value as an index into the array and negate the entry there to mark a first visit; encountering an already-negative entry means the value has been seen before.

Loading animation…

Intuition

Every value v belongs to the index v-1, so the array can remember which values it has already touched. The first time we land on a slot we flip its sign to record the visit. If we ever arrive at a slot that is already negative, the value that maps to it must have been visited earlier, which can only happen when that value appears a second time. Reading absolute values throughout keeps the traversal correct even after signs have been altered.

Algorithm walkthrough

1Iterate over the array; for each entry take its absolute value and compute the target index as that value minus one.
2If the number sitting at the target index is already negative, the value has been seen once before, so record it as a duplicate.
3Otherwise, negate the number at the target index to mark this value as seen.
4Continue to the end; the collected values are exactly the ones appearing twice.

Implementation

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        result = []
        for x in nums:
            idx = abs(x) - 1
            if nums[idx] < 0:
                result.append(idx + 1)
            else:
                nums[idx] = -nums[idx]
        return result

Time

O(n)

Space

O(1) beyond the output list

The input array is mutated in place to store visit markers.

Create a free account to see the solution

You get the step-by-step animation, the intuition and clean code in every language. Free, no credit card.

Create a free account Already have an account? Sign in

Back to Arrays

After the pattern

Now solve one you haven't seen.

Twice-Scanned Bin Labels is our own problem on the technique behind Find All Duplicates in an Array: a new statement, so there's no answer to remember. Write it in your browser and run it against graded tests.

Practise it with tests All practice problems

1,194 problems · 15,062 graded tests · free