Site icon Study Algorithms

[Leetcode] : Find All Duplicates in an Array Solution

Let us try to understand the problem statement first. You have an array of integers, where some of the elements are duplicated. Find all the duplicates present in the array and give them as an output.

For example if the array is given as arr[] = {4, 3, 2, 8, 2, 3, 1}. Elements 3 and 2 are appearing twice. Hence, this should be your answer. Return an empty array if there are no duplicates.

Fig: Sample test cases to find array duplicates

Method 1: Using a HashSet

Let us take up a sample input array arr [] = {4, 3, 2, 8, 2, 3, 1}

Fig: Array to find duplicates

One way to solve this problem is to use a HashSet. A HashSet is a set data structure that does not allow you to add duplicate values. For example, if the set has values {2, 3, 5} and you try to add 5 again, it will not be added to the set.

Here is how we can find the duplicates in the array using this method:

Code:

  public List<Integer> findDuplicatesLinearSpace(int[] nums) {

    List<Integer> resultSet = new ArrayList<>();

    // Set to store unique numbers
    Set<Integer> uniqueSet = new HashSet<>();
    for (int num : nums) {

      // If already present, then it is a duplicate
      if (uniqueSet.contains(num))
        resultSet.add(num);

      // Add the number to the set
      uniqueSet.add(num);
    }

    return resultSet;
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(n)

Method 2: Using constant space

The tricky part about this problem is to solve it in constant space. In the above method we just discussed, you need an extra space of O(n). That is because each element could occur once. The problem challenges you to solve this in constant space. Let us take up the array once again arr[] = {4, 3, 2, 8, 2, 3, 1}

Fig: Sample test case

You are also given a condition that no element of the array would be smaller than 0 and larger than the size of the array. This gives you a very interesting hint about the solution. Each element in the array is a valid position in the array also.

Fig: Elements can be used to reference positions in array

We can use property to our advantage. So element 4 could also point at arr[4]. This way if we are looking at arr[4] twice, this means that 4 is repeated in the array and is a duplicate. We have to make sure that we are not using any extra space. To make this possible make the element negative. This helps to keep a track of the visited element.

Code:

  public List<Integer> findDuplicatesConstantSpace(int[] nums) {

    List<Integer> resultSet = new ArrayList<>();

    for (int i = 0; i < nums.length; i++) {
      // Get the index, the element corresponds to
      int index = Math.abs(nums[i]) - 1;

      // If the number is already negative, it means we are 
      // encountering it twice
      if (nums[index] < 0)
        resultSet.add(index + 1);

      // Flip the number at the index to negative
      nums[index] = nums[index] * -1;
    }

    return resultSet;
  }
Code language: Java (java)

Time Complexity: O(n)
Space Complexity: O(1)

As always, the code and test cases are available on Github.

Video Explanation:

Exit mobile version