Find All Duplicates in an Array

Medium
183.

Find All Duplicates in an Array

Find All Duplicates in an Array is a medium coding problem on arrays and hash table, asked in Amazon, Google, Microsoft and Flipkart interviews.

Given an integer array nums of length n where every nums[i] is in the range [1, n] and each value appears once or twice, return all the values that appear twice, in increasing order.

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

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= nums.length
  • Each element appears once or twice.

Follow-up: Can you do it in O(n) time using only the output array as extra space?

Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findDuplicates = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Find All Duplicates in an Array — Problem & Solution

Find All Duplicates in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Find All Duplicates in an Array is a medium coding problem on arrays and hash table, asked in Amazon, Google, Microsoft and Flipkart interviews.

Problem statement

Given an integer array nums of length n where every nums[i] is in the range [1, n] and each value appears once or twice, return all the values that appear twice, in increasing order.

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

  • 1 <= nums.length <= 40
  • 1 <= nums[i] <= nums.length
  • Each element appears once or twice.

Follow-up: Can you do it in O(n) time using only the output array as extra space?

Hints for Find All Duplicates in an Array

  1. Hint 1

    The values are confined to 1..n, which means each one can index the array itself.

  2. Hint 2

    Counting occurrences in an array of size n + 1 is the direct O(n) solution.

  3. Hint 3

    For O(1) extra space, negate nums[abs(v) - 1] as a visited mark — meeting an already-negative slot means the second sighting.

How to solve Find All Duplicates in an Array

Values are confined to 1..n, so a counting array of size n + 1 records each value's frequency; report those counted twice.

Approach

  1. Allocate count of size n + 1.
  2. Increment count[x] for each element.
  3. Collect every v in 1..n with count[v] == 2, in increasing order.

Why it works

Iterating v from 1 to n visits values in sorted order, so the output is sorted without an explicit sort.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • For O(1) extra space, negate nums[|v| - 1] as a visited mark and report |v| when the slot is already negative — then sort the result.
  • A hash set works but the bounded range makes the array strictly better.

Reference solution

Python

def findDuplicates(nums):
    count = [0] * (len(nums) + 1)
    for x in nums:
        count[x] += 1
    return [v for v in range(1, len(nums) + 1) if count[v] == 2]

Java

public static int[] findDuplicates(int[] nums) {
    int[] count = new int[nums.length + 1];
    for (int x : nums) count[x]++;
    List<Integer> out = new ArrayList<>();
    for (int v = 1; v <= nums.length; v++) {
        if (count[v] == 2) out.add(v);
    }
    int[] res = new int[out.size()];
    for (int i = 0; i < res.length; i++) res[i] = out.get(i);
    return res;
}

C++

vector<int> findDuplicates(vector<int>& nums) {
    vector<int> count(nums.size() + 1, 0);
    for (int x : nums) count[x]++;
    vector<int> out;
    for (int v = 1; v <= (int) nums.size(); v++) {
        if (count[v] == 2) out.push_back(v);
    }
    return out;
}

JavaScript

var findDuplicates = function(nums) {
    const count = new Array(nums.length + 1).fill(0);
    for (let i = 0; i < nums.length; i++) count[nums[i]]++;
    const out = [];
    for (let v = 1; v <= nums.length; v++) {
        if (count[v] === 2) out.push(v);
    }
    return out;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets