MediumArrayHash Table

Find All Duplicates in an Array

1 approach, code in all languages

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 unlock the solution

See 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

You've got the patterns

Patterns get you through the screen. Shipping gets you hired.

FDE Coach is a cohort-based program in frontend, backend, AWS, and AI where you build real products and get referred to 200+ hiring partners. The free live workshop is the fastest way to see how we teach.

Join the free workshop Explore the program

750+ engineers trained · frontend, backend, AWS & AI