Lets Code Everyday

Question - 30:

Find All Duplicates in an Array

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 appears 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: []

First approach:

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> set= new HashSet<>();
        Set<Integer> resultSet=new HashSet<>();
        for(int num:nums){
            if(set.add(num)) continue;
            else resultSet.add(num);
        }
    return new ArrayList<>(resultSet);      
    }
}

Step-by-step implementation:

The code defines a class called Solution with a method findDuplicates that takes an array of integers nums as input and returns a list of integers.
Inside the method, two sets are created: set and resultSet. These sets are used to keep track of unique elements encountered in the nums array and the elements that are duplicates, respectively.
A for-each loop is used to iterate over each element num in the nums array.
Within the loop, the code checks if the element num can be added to the set using the add() method. If the element is successfully added (i.e., it is not a duplicate), the loop continues to the next iteration using the continue statement.
If the element num cannot be added to the set because it already exists (i.e., it is a duplicate), the code adds it to the resultSet using the add() method.
After iterating over all elements in the nums array, the resultSet is converted to a list using the ArrayList constructor.
Finally, the method returns the resultSet as a list of duplicates found in the nums array.

Time Complexity: The time complexity of the code is O(n), where n is the length of the input array nums. This is because the code iterates over each element in the array once using a for-each loop. The operations performed inside the loop, such as adding elements to sets, have an average time complexity of O(1) for hash sets. Therefore, the overall time complexity is linear with respect to the size of the input array.

Space Complexity: The space complexity of the code is O(n), where n is the length of the input array nums. This is because two sets, set and resultSet, are used to store unique elements and duplicate elements, respectively. In the worst-case scenario, when all elements in the nums array are unique, both sets will contain all n elements. Therefore, the space required is proportional to the size of the input array.

Second approach:

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
       Map<Integer,Integer> freqMap=new HashMap<>();
       for(int num:nums){
           int val=freqMap.getOrDefault(num,0);
           freqMap.put(num,val+1);
       }
       List<Integer> resList=new ArrayList<>();
       for(Map.Entry<Integer,Integer> map:freqMap.entrySet()){
           if(map.getValue()>1) resList.add(map.getKey());
       }
    return resList;     
    }
}

Step-by-step implementation:

The code defines a class called Solution with a method findDuplicates that takes an array of integers nums as input and returns a list of integers.
Inside the method, a freqMap is created as a HashMap. This map will store the frequency of each element in the nums array.
A for-each loop is used to iterate over each element num in the nums array.
Inside the loop, the code retrieves the current frequency of the element num from the freqMap using the getOrDefault() method. If the element is not present in the map, it returns a default value of 0.
The code then puts the updated frequency of the element num in the freqMap by using the put() method, incrementing the frequency by 1.
After iterating over all elements in the nums array, a new resList is created as an empty ArrayList. This list will store the duplicates found.
Another loop is used to iterate over each entry in the freqMap using the entrySet() method.
Inside the loop, the code checks if the frequency of the current entry is greater than 1. If it is, it means the corresponding element is a duplicate, so it is added to the resList using the add() method.
Finally, the resList containing the duplicates is returned as the result.

Time Complexity: The time complexity of this implementation is O(n), where n is the length of the input array nums. The first loop that iterates over the nums array has a linear time complexity. The second loop that iterates over the freqMap entries also has a linear time complexity since the number of entries is at most equal to the number of distinct elements in the array. Therefore, the overall time complexity is linear with respect to the size of the input array.

Space Complexity: The space complexity of this implementation is O(n), where n is the length of the input array nums. The freqMap stores the frequencies of elements in the array, and in the worst-case scenario, it can contain all n elements if all elements in the array are unique. Additionally, the resList may contain duplicates, but its size is limited by the number of distinct elements. Hence, the overall space complexity is proportional to the size of the input array.

Third approach:

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        int n=0;
        for(int num:nums) n=Math.max(n,num);
            int[] arr= new int[n];

        for(int i=0;i<nums.length;i++){
            if(arr[nums[i]-1]==0) arr[nums[i]-1]=1;
            else arr[nums[i]-1]=arr[nums[i]-1]+1;
        }
        List<Integer> list= new ArrayList<>();
        for(int i=0;i<arr.length;i++){
             if(arr[i]>1) list.add(i+1);
        }
    return list; 
    }
}

Step-by-step implementation:

The code defines a class called Solution with a method findDuplicates that takes an array of integers nums as input and returns a list of integers.
Inside the method, a variable n is initialized as 0. This variable will be used to determine the size of the arr array.
A for-each loop is used to iterate over each element num in the nums array. Inside the loop, the maximum value between n and the current element num is determined using the Math.max() method. This is done to find the maximum value in the nums array.
After iterating over all elements in the nums array, an array arr is created with a size equal to the maximum value n determined in the previous step. The purpose of this array is to store the count of occurrences of each element in nums.
Another loop is used to iterate over each element in the nums array. Inside the loop, the code checks if the count of the current element in arr is 0. If it is 0, it means this is the first occurrence of the element, so the count is set to 1. Otherwise, if the count is not 0, it means the element is a duplicate, so the count is incremented by 1.
After counting the occurrences of each element in the nums array, a new list is created as an empty ArrayList. This list will store the duplicates found.
Another loop is used to iterate over each element in the arr array. Inside the loop, the code checks if the count of the current element is greater than 1. If it is, it means the corresponding element is a duplicate, so it is added to the list.
Finally, the list containing the duplicates is returned as the result.

Time Complexity: The time complexity of this implementation is O(n), where n is the length of the input array nums. The first loop that iterates over the nums array has a linear time complexity. The second loop that iterates over the arr array also has a linear time complexity since it depends on the number of elements in the array. Therefore, the overall time complexity is linear with respect to the size of the input array.

Space Complexity: The space complexity of this implementation is O(n), where n is the maximum value in the input array nums. The arr array is created with a size equal to the maximum value, and in the worst-case scenario, it can contain all n elements if all elements in the array are unique. Additionally, the list may contain duplicates, but its size is limited by the number of distinct elements. Hence, the overall space complexity is proportional to the maximum value in the input array.

Conclusion:

Both the first and second implementations are more favorable in terms of space efficiency since they require space proportional to the size of the input array. The choice between them depends on factors such as the specific requirements of the problem and the nature of the input data. The third implementation, while still linear in time complexity, may not be as preferable due to its higher space complexity.