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.
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: []
In order to detect duplicates, we must need to track the items which have already occurred. There can be two solutions:
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.
The time complexity of the above algorithm is O(n) since we iterate through the input array only once.
In case you want to see the code used in this article, please see this GitHub URL
If you found this post useful, please subscribe. This will enable you to be notified whenever I write something new. If you don't like subscribing to newsletters, please subscribe to RSS + Web feeds.
In case you subscribe to the newsletter, your email will not be shared with advertisers, you will not be spammed, and you can unsubscribe at any moment.