# Find All Duplicates in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/find-all-duplicates-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/find-all-duplicates-in-an-array
**Data structures:** Array, Hash Table
**Companies:** [Pocket Gems](https://scaleengineer.com/companies/pocket-gems)
---
## Problem
Given an integer array `nums` of length `n` where all the integers of `nums` are in the range `[1, n]` and each integer appears **at most** **twice**, return _an array of all the integers that appears **twice**_.

You must write an algorithm that runs in `O(n)` time and uses only _constant_ auxiliary space, excluding the space needed to store the output

**Example 1:**

**Input:** nums = [4,3,2,7,8,2,3,1]
**Output:** [2,3]

**Example 2:**

**Input:** nums = [1,1,2]
**Output:** [1]

**Example 3:**

**Input:** nums = [1]
**Output:** []

**Constraints:**

* `n == nums.length`
* `1 <= n <= 105`
* `1 <= nums[i] <= n`
* Each element in `nums` appears **once** or **twice**.

# Approaches
## Brute Force
The most straightforward approach is to compare every element with every other element in the array. This method is easy to conceive but highly inefficient.
**Time:** O(n^2) - Due to the nested loops, for each element, we scan the rest of the array. · **Space:** O(1) - We only use a few variables and the result list. The auxiliary space is constant, as the space for the output is excluded from consideration.
**Pros:** Simple to understand and implement.; Uses constant extra space (excluding the output list).
**Cons:** Extremely inefficient with a time complexity of O(n^2).; Will likely result in a 'Time Limit Exceeded' error for large inputs.
### Explanation
We use two nested loops to find pairs of equal numbers. The outer loop iterates from the first element to the last, and the inner loop iterates from the next element of the outer loop's current position. If two elements `nums[i]` and `nums[j]` are found to be equal, we've identified a duplicate. To prevent adding the same duplicate number to our result list multiple times (e.g., for an input like `[2, 2, 2]`), we can check if the number is already in our result list before adding it.

```java
import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    // Check if this duplicate is already found
                    if (!duplicates.contains(nums[i])) {
                        duplicates.add(nums[i]);
                    }
                    break; // Move to the next i
                }
            }
        }
        return duplicates;
    }
}
```
### Algorithm
1. Initialize an empty list `duplicates` to store the results.
2. Iterate through the array with an index `i` from `0` to `n-2`.
3. For each element `nums[i]`, start an inner loop with index `j` from `i+1` to `n-1`.
4. Inside the inner loop, compare `nums[i]` and `nums[j]`.
5. If `nums[i] == nums[j]`, it's a duplicate. Check if this number is already in the `duplicates` list. If not, add it.
6. Return the `duplicates` list.

## Sorting the Array
A significant improvement over the brute-force method is to first sort the array. Once sorted, any duplicate numbers will be grouped together, making them easy to find in a single pass.
**Time:** O(n log n) - This is the time complexity for most standard sorting algorithms, like Merge Sort or Quick Sort. · **Space:** O(log n) or O(n) - The space complexity depends on the sorting algorithm used. For instance, Java's `Arrays.sort()` for primitives uses a variant of Quicksort which requires O(log n) stack space on average.
**Pros:** Much more efficient than the brute-force approach.; Relatively simple logic after the sorting step.
**Cons:** The time complexity is dominated by the sort, which is not linear.; The space complexity of standard sorting algorithms is typically not O(1), thus violating one of the problem's constraints.; Modifies the original array.
### Explanation
The core idea is that after sorting, if an element is a duplicate, it will be identical to the element immediately preceding it. We can sort the input array `nums` and then iterate through it from the second element. In each step, we compare the current element `nums[i]` with the previous one `nums[i-1]`. If they are the same, we have found a duplicate and add it to our result list.

```java
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Arrays.sort(nums);
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] == nums[i-1]) {
                duplicates.add(nums[i]);
            }
        }
        return duplicates;
    }
}
```
### Algorithm
1. Sort the input array `nums` in non-decreasing order.
2. Initialize an empty list `duplicates`.
3. Iterate through the sorted array from the second element (index `1`) to the end.
4. For each element `nums[i]`, compare it with the previous element `nums[i-1]`.
5. If `nums[i] == nums[i-1]`, add `nums[i]` to the `duplicates` list.
6. Return the `duplicates` list.

## Using a Hash Set
A linear time complexity solution can be achieved using a hash set to keep track of the numbers encountered. This approach trades space for time.
**Time:** O(n) - We iterate through the n elements of the array once. Hash set operations (add, contains) take O(1) time on average. · **Space:** O(n) - In the worst case, the hash set might need to store up to n/2 + 1 elements if half the numbers are duplicates and the other half are unique.
**Pros:** Achieves optimal O(n) time complexity.; The logic is straightforward and easy to reason about.
**Cons:** Requires O(n) extra space for the hash set, which violates the problem's constant space constraint.
### Explanation
We can iterate through the array `nums` once. For each number, we check if it's already present in a hash set. If it is, we've found a duplicate and add it to our result list. If it's not, we add the number to the hash set to mark that we've seen it. The hash set provides average O(1) time for lookups and insertions, making the overall algorithm very fast.

```java
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        Set<Integer> seen = new HashSet<>();
        List<Integer> duplicates = new ArrayList<>();
        for (int num : nums) {
            if (seen.contains(num)) {
                duplicates.add(num);
            } else {
                seen.add(num);
            }
        }
        return duplicates;
    }
}
```
### Algorithm
1. Initialize an empty list `duplicates`.
2. Initialize an empty hash set `seen`.
3. Iterate through each number `num` in the input array `nums`.
4. For each `num`, check if it exists in the `seen` set.
5. If `seen.contains(num)` is true, it's a duplicate, so add `num` to the `duplicates` list.
6. If it's not in the set, add `num` to `seen`.
7. After the loop finishes, return the `duplicates` list.

## In-place Marking using Negation
This is the optimal solution that satisfies both the O(n) time and O(1) space constraints. It cleverly uses the input array itself as a hash map by modifying the sign of the elements to mark them as 'seen'.
**Time:** O(n) - We perform a single pass through the array of length n. · **Space:** O(1) - We do not use any extra space other than the list for the result. The modifications are done in-place.
**Pros:** Achieves O(n) time complexity.; Achieves O(1) auxiliary space complexity, meeting all problem constraints.; Very efficient and clever use of the input array's properties.
**Cons:** This approach modifies the input array. If the problem required preserving the original array, this method would not be suitable without making a copy first (which would violate the space constraint).; The logic can be less intuitive at first glance compared to using a hash set.
### Explanation
The problem states that all integers are in the range `[1, n]`. This allows us to use the value of an element to map to an index in the array (specifically, number `x` can be mapped to index `x-1`).

We iterate through the array. For each element `nums[i]`, we take its absolute value, let's call it `val`. This `val` corresponds to the index `val - 1`. We then look at the number at this index, `nums[val - 1]`. 
- If `nums[val - 1]` is negative, it means we have already encountered the number `val` before. Thus, `val` is a duplicate, and we add it to our result list.
- If `nums[val - 1]` is positive, it's the first time we are seeing the number `val`. We mark it as 'seen' by negating the number at that index: `nums[val - 1] = -nums[val - 1]`.

We must use `Math.abs(nums[i])` because the element at the current position `i` might have been negated by a previous step in the iteration.

```java
import java.util.ArrayList;
import java.util.List;
import java.lang.Math;

class Solution {
    public List<Integer> findDuplicates(int[] nums) {
        List<Integer> duplicates = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int index = Math.abs(nums[i]) - 1;
            
            // If the number at this index is already negative, 
            // it means we have seen this number before, so it's a duplicate.
            if (nums[index] < 0) {
                duplicates.add(index + 1);
            }
            
            // Mark the number at this index as seen by making it negative.
            nums[index] = -nums[index];
        }
        return duplicates;
    }
}
```
### Algorithm
1. Initialize an empty list `duplicates`.
2. Iterate through the array `nums` from index `i = 0` to `n-1`.
3. For the current number `nums[i]`, get its absolute value and find the corresponding index: `index = Math.abs(nums[i]) - 1`.
4. Check the sign of the element at `nums[index]`.
5. If `nums[index]` is negative, it means the number `index + 1` has been seen before. Add `index + 1` to the `duplicates` list.
6. If `nums[index]` is positive, change its sign to mark it as seen: `nums[index] = -nums[index]`.
7. After the loop, return the `duplicates` list.

# Solutions
### Java

```java
class Solution {
public
  List<Integer> findDuplicates(int[] nums) {
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      while (nums[i] != nums[nums[i] - 1]) {
        swap(nums, i, nums[i] - 1);
      }
    }
    List<Integer> ans = new ArrayList<>();
    for (int i = 0; i < n; ++i) {
      if (nums[i] != i + 1) {
        ans.add(nums[i]);
      }
    }
    return ans;
  }
  void swap(int[] nums, int i, int j) {
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
}

```

### CPP

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

```

### Python

```python
class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]: for i in range(len(nums)): while nums[i] != nums[nums[i] - 1]: nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1] return [v for i, v in enumerate(nums) if v != i + 1]

```