Find numbers that appear twice in an array.

Learn how to create an algorithm to find the numbers that appear twice in an array while others appear once.

Given an array of integers 1 < a[i] < n (n is the length of the array), some elements appear twice while others appear once.

We have to find all the elements that appear twice.

Example

Input:
[4,3,2,7,8,2,3,1]

Output:
[2,3]

Find numbers that appear twice in an array while rest appear once.

Most simple approach to solve this problem is use a has hashmap to calculate the count of the elements in the array and the get all the elements from the hashmap which has count 2.

It will run in O(n) time and take O(n) space.

There is another optimal solution which takes constant space.

Implementation

• First get the value of the array and use it as an index because this way if number is appear twice then will be able to track it.
• Multiply the array element at that given value (index) with a negative number say -1.
• If a number have appeared once then the value in the array at that index will be negative else it will be positive if it has appeared twice (-1 * -1 = 1).
• Find the element with positive value and return their index.

We are using the forEach method of array which iterates each element of the array and returns a callback function which includes the element, index, and the original array.

Thus we are changing the original array in place so it does not requires extra space.

const findDuplicates = (nums) => {
    //To store the numbers that appeared twice
    let result = [];
    
    //Itearte each element
    nums.forEach((val, ind, arr) => {
        
        //Use the value as index
        let temp = Math.abs(arr[ind]) - 1;
        
        //If the number is already negative
        //That means it has appeared once and this is its second time.
        //So add it in the result
        if(arr[temp] < 0){
            result.push(temp+1);
        }
        
        //Multiply the element at the given index with negative number
        arr[temp]*= -1;
    });
    
    return result;
};

Input:
console.log(findDuplicates([4,3,2,7,8,2,3,1]));
console.log(findDuplicates([2,3,5,6,6,7,7,8]));

Output:
[2, 3]
[6, 7]

Time complexity: O(n).
Space complexity: O(1).