Home Arrays [Leetcode] : Find All Duplicates in an Array Solution

[Leetcode] : Find All Duplicates in an Array Solution

by nikoo28
4 comments

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.

Image showing sample test cases with found 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}

image showing an array to find duplicates from
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:

  • Create a HashSet that will store all the unique integers.
  • Create a resultSet that will have all the duplicate integers.
  • Iterate through all elements of the array and add it to the set.
  • If the element is already present in the set, you can add the element to the result set.
  • Return the result set.

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}

image showing an array to find duplicates from
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.

Image showing the importance of given limit.
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.

  • Start traversing each element in the array.
  • For each element, navigate to the position in the array.
  • If the element is positive, make it negative.
  • If the element is already negative, it means we were already here, hence add the element to the list of duplicates.
  • At the end return the duplicate set.

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:

4 comments

You may also like

4 comments

ODI March 25, 2021 - 05:55

But it’s not only a mutation of the original array – we also have the returned resultSet, which takes space. Shouldn’t we consider that resultSet as part of our space complexity?

Reply
nikoo28 March 25, 2021 - 09:30

Like I said earlier, you only need to account for “extra” space, you use to solve the problem. You do not count the memory for input and output. It is always assumed you have enough memory for them.

Reply
odi March 23, 2021 - 11:56

Not sure why is that an O(1). Potentially, the first n/2 items of the array could be the set of numbers 1 to (n/2)-1, and then the second set could be that same set as well.

For example, with an array of size 100, the first 50 numbers will be 1,2, … 50, and the second half will be those same numbers.

Your solution then gives us O(n/2) space complexity.

Reply
nikoo28 March 23, 2021 - 21:46

To calculate the space complexity, you only take into account the “EXTRA” space your code is taking. In the solution I described above, we are just mutating the original array elements, hence no additional space is required. This gives you a space complexity of O(1).

Reply

Enclose codes in [code lang="JAVA"] [/code] tags

This site uses Akismet to reduce spam. Learn how your comment data is processed.

This website uses cookies to improve your experience. We'll assume you're ok with this, but you can opt-out if you wish. Accept Read More