How to solve LeetCode problem about finding all duplicates in an array

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:

To detect duplicates, we just 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 lookup operation, hence each iteration of the first loop will do a lookup 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 a 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 lookup 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.

/**
* returns duplicates from an array
*/

function findDuplicates(inputArray) {
    let inputHashMap = {};
    let dupplicates = [];

    for (let i=0; i < inputArray.length; i++) {
        if (typeof inputHashMap[inputArray[i]] === 'number') {
            dupplicates.push(inputArray[i]);
        } else {
            inputHashMap[inputArray[i]] = inputArray[i];
        }
    }

    return dupplicates;
}

const testData = [[4,3,2,7,8,2,3,1], [1,1,2], [1]]

// invoking solution for each test data item
testData.forEach(d => {
    console.log(findDuplicates(d));
})

Note: Concerning the discussion on tweet, updated the if condition of 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 the element is not found in the inputHashMap, we add it to the inputHashMap since it is a new element.

• At the end of the 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:

For those who prefer a visual guide, you can also check out the video walkthrough for this problem on YouTube using this URL: Developer Log 1 | LeetCode 442 | Find All Duplicates in an Array | Code with Asad. This video will walk you through the problem and navigate through this problem in detail. With this article and the video, you will be well-equipped to solve the problem on LeetCode using JavaScript.

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