# Find All Duplicates in an Array LeetCode Solution

Difficulty Level Medium

## Problem Statement

The problem, Find All Duplicates in an Array LeetCode Solution states that you are given an array of size `n` containing elements in the range `[1,n]`. Each integer can appear either once or twice and you need to find all the elements that appear twice in the array. ### Examples for Find All Duplicates in an Array LeetCode Solution

Test Case 1 –

Input – [4, 3, 2, 7, 8, 2, 3, 1]

Output – [2, 3]

Test Case 2 –

Input – [1, 1, 2]

Output – 

Test Case 3 –

Input – 

Output – []

## Approach

### Idea

1. The first catch in the question is that the numbers present in the array are from 1 to n inclusive, where n is the size of the array. So we can do some manipulations on the indices of the array.
2. Consider the test case – [1, 2, 3, 4, 4]. The corresponding indices will be 0, 1, 2, 3, 3 i.e. `nums[i] - 1`.
3. As we traverse the array, we mark the index corresponding to that element. By marking, we mean `nums[abs(nums[i])-1] = -1*nums[abs(nums[i])-1]`.
4. In the same traversal, if we encounter a negative element at some index, it means that the index has already been marked earlier and is a duplicate element. So we push that element (index) to the output array.

if an element `x` occurs just once in the array, the value at index `abs(x)-1` becomes negative and remains so for all of the iterations that follow.

1. Traverse through the array. When we see an element `x` for the first time, we’ll negate the value at the index `abs(x)-1`.
2. But, the next time we see an element, we don’t need to negate it again! If the value at the index `abs(x)-1` is already negative, we know that we’ve seen element `x` before.

### Code for Find All Duplicates in an Array LeetCode Solution

#### C++

```class Solution {
public:
vector<int> findDuplicates(vector<int>& nums) {
vector<int> ans;
int n = nums.size();
for(int i=0;i<n;i++){
if(nums[abs(nums[i])-1] < 0) ans.push_back(abs(nums[i]));
nums[abs(nums[i])-1] = -1*nums[abs(nums[i])-1];
}
return ans;
}
};
```

#### JAVA

```class Solution {
public List<Integer> findDuplicates(int[] nums) {
List<Integer> ans = new ArrayList<>();
int n = nums.length;
for(int i=0;i<n;i++){
nums[Math.abs(nums[i])-1] = -1*nums[Math.abs(nums[i])-1];
}
return ans;
}
}```

#### Python

```class Solution(object):
def findDuplicates(self, nums):
ans = []
for i in nums:
if nums[abs(i)-1] < 0:
ans.append(abs(i))
nums[abs(i)-1] = -1*nums[abs(i)-1]
return ans
"""
:type nums: List[int]
:rtype: List[int]
"""
```

## Complexity Analysis for Find All Duplicates in an Array LeetCode Solution

### Time Complexity

Since we are traversing the array only once, the time complexity for the approach is O(n).

### Space Complexity

We are not using any auxiliary space in the algorithm, so the space complexity is O(1).

Translate »