All methods to find all duplicates in an array | Leetcode 442 Solution

All methods to find all duplicates in an array | Leetcode 442 Solution

Table of contents

Link : https://leetcode.com/problems/find-all-duplicates-in-an-array/description/

Solution link : https://leetcode.com/problems/find-all-duplicates-in-an-array/solutions/3695445/mimicking-interview-all-approaches-explained-easy-trick-and-tips/

Intuition

Duplicates can be found in various ways. Given below are the approaches:

You:
1- We have a range [1,n], so we traverse the array and check for how many times every element is appearing in the array. This algorithm would have O(n^2) time complexity and O(1) space complexity.
2- But we can have a better approach of traversing the array only once and storing the elements and their frequency using hashing. This way we can reduce our time complexity to O(n) but we need an extra space here so it will result in O(n) space complexity.

The interviewer will ask you to optimize it.
3- We can reduce the space by sorting the array. We will sort the array and check for duplicates.
In java, the Arrays.sort() method uses a variant of quick sort for primitives, so we would have O(nlogn) time complexity and the space complexity is reduced to O(log n).
4- As we have every element of the array in range [1,n], the best sorting algorithm would be Cyclic Sort, and after sorting the array via cyclic sort we would have duplicates taking the place of missing elements in the array. So after sorting we would traverse through the array and see for elements not at their correct indexes i.e. their must a duplicate element present at their correct index, so in this way we can have all the duplicates in O(n) time complexity and constant space complexity O(1).

Approach

The best way to approach question having elements range [1,n], is to use cyclic sort.
Use this tip whenever you see elements range [1,n].

Complexity

  • Time complexity: O(n)

  • Space complexity: O(1)

Code

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> ans = new ArrayList<Integer>();
        int i = 0;
        while(i < nums.length){
            if(nums[i] != nums[nums[i]-1]){ //swap
                int temp = nums[nums[i]-1];
                nums[nums[i]-1] = nums[i];
                nums[i] = temp;
            } else{
                i++;
            }
        }

        //traverse through the array and the duplicate elements will be at the place of missing elements
        for(i = 0; i< nums.length; i++){
            if(nums[i] != i+1){
                ans.add(nums[i]);
            }
        }

        return ans;
    }
}