Find All Duplicates in an Array

Find All Duplicates in an Array is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Array - Cyclic Sort subpattern.

Problem statement

Given an integer array nums of length n where all the integers of nums are in the range [1, n] and each integer appears at most twice, return an array of all the integers that appears twice.

You must write an algorithm that runs in O(n) time and uses only constant auxiliary space, excluding the space needed to store 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 <= 105

- 1 <= nums[i] <= n

- Each element in nums appears once or twice.

Topics and companies

Topics: Array, Hash Table.

Reported in interviews at Amazon, Facebook, Microsoft, Bloomberg, Docusign.

How to practise Find All Duplicates in an Array on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(1) space.

Open Find All Duplicates in an Array in the code editor, or read the Find All Duplicates in an Array editorial for a worked solution with its approach and complexity analysis.

Where Find All Duplicates in an Array sits in the DSA pattern sheet

• Array/Matrix Manipulation Patterns pattern guide
• Array - Cyclic Sort subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Find All Duplicates in an Array

Other problems that use the same Array - Cyclic Sort and Array/Matrix Manipulation Patterns techniques:

• Find All Numbers Disappeared in an Array — Easy, same subpattern
• First Missing Positive — Hard, same subpattern
• Add Binary — Easy, same pattern
• Add to Array-Form of Integer — Easy, same pattern
• Diagonal Traverse — Medium, same pattern
• Game of Life — Medium, same pattern