Find duplicates in an array (DSA)

 

Problem statement:(👈click here for GFG)

Given an array a[] of size N which contains elements from 0 to N-1, you need to find all the elements occurring more than once in the given array.

Note: The extra space is only for the array to be returned.

Try and perform all operations within the provided array. 

Example 1:

Input:
N = 4
a[] = {0,3,1,2}
Output: -1
Explanation: N=4 and all elements from 0
to (N-1 = 3) are present in the given
array. Therefore output is -1.

Example 2:

Input:
N = 5
a[] = {2,3,1,2,3}
Output: 2 3 
Explanation: 2 and 3 occur more than once
in the given array.

Your Task:
Complete the function duplicates() which takes array a[] and n as input as parameters and returns a list of elements that occur more than once in the given array in a sorted manner. If no such element is found, return list containing [-1]. 

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).

Constraints:
1 <= N <= 105
0 <= A[i] <= N-1, for each valid i

Solution: for geeks

class Solution {
    
    duplicates(a, n)
    {
        //your code here
    let obj = {};
    for(let i = 0; i < n; i++){
        let key = a[i];
        if(obj[key] === undefined){
            obj[key] = 1;
        }
        else{
            obj[key]++;
        }
    }
    let bag = [];
    let hasDuplicates = false;
    for(let key in obj){
        if(obj[key] > 1){
            bag.push(parseInt(key));
            hasDuplicates = true;
        }
    }
    if(!hasDuplicates){
        return [-1];
    }
    return bag.sort((a,b) => a-b);
    }
}

Solution:

class Solution {
    
    duplicates(a, n)
    {
        //your code here
         let res = [];
        for(let i=0;i<n;i++){
            let index = a[i] % n;
            if(a[index] >= n){
                if(a[index] < 2*n){
                    res.push(index);
                }
            }
            a[index] += n;
        }
        if(res.length === 0){
            return [-1];
        }
        return res.sort((a,b) => a-b);
    }
}