Introduction

In this article, we will discuss the solution to LeetCode problem #422 — "Find All Duplicates in an Array" using JavaScript. The problem statement requires us to find all the elements that appear twice in a given array. The constraints require us to solve the problem in O(n) time and use only constant extra space. We will start by discussing the problem in detail and then move on to the approach we can take to solve it efficiently.

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 once or twice, return an array of all the integers that appear twice.

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.

Approach:

In order to detect duplicates, we must need to track the items which have already occurred. There can be two solutions:

• One can be brute force with a nested loop. We can start from the first element in the iteration, and then compare it against all the entries in the array to see if it has a duplicated value or not.
  • This approach will have a time complexity of O(n^2).
  • If we revisit our understanding of the data structures, we know that array has an O(n) time complexity of look up operation, hence each iteration of first loop will do a look up which will result in O(n^2).
• We need to somehow eliminate the second loop. There is another data structure in the form of Objects/Key value pairs in JS which have some characteristics of a hash map primarily constant time lookup operation. That is what we need to eliminate nested iteration. Hence we use an object to track the duplicate and its constant look up operation gives us an O(n) time complexity for the solution.

To solve the given problem, we will create a hash map to store the frequency of elements of the input array. We will iterate through each element in the input array and add its frequency to the hash map. If the frequency is already present in the hash map, then the element is a duplicate and we can add it to the duplicates array.

1/**
2* returns duplicates from an array
3*/
4
5function findDuplicates(inputArray) {
6    let inputHashMap = {};
7    let dupplicates = [];
8
9    for (let i=0; i < inputArray.length; i++) {
10        if (inputHashMap[inputArray[i]]) {
11            dupplicates.push(inputArray[i]);
12        } else {
13            inputHashMap[inputArray[i]] = inputArray[i];
14        }
15    }
16
17    return dupplicates;
18}
19
20const testData = [[4,3,2,7,8,2,3,1], [1,1,2], [1]]
21
22// invoking solution for each test data item
23testData.forEach(d => {
24    console.log(findDuplicates(d));
25})

Note: Concerning the discussion on this tweet, updated the if condition for checking the existence of an element of the array inside the hashmap.

The function findDuplicates takes an input array as an argument and returns an array containing all the duplicate elements.

• We start by initializing an empty duplicates array to store the duplicates.
• We then iterate through each element in the input array using a for loop.
• We see if the current element is part of inputHashMap. If it is found, then we add the current element to the duplicates array since it is a duplicate. If element is not found in the inputHashMap, we add it to the inputHashMap since it is new element.
• At the end of loop, we return the duplicates array.
• We iterate the testData to invoke each test case against our solution.

Time Complexity

The time complexity of the above algorithm is O(n) since we iterate through the input array only once.

Ending Notes:

In case you want to see the code used in this article, please see this GitHub URL