*1.9K*

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.

#### Method 1: Using a HashSet

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

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}`

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.

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.

## 4 comments

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?

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.

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.

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).

Comments are closed.