#### Approach #1 Brute Force [Time Limit Exceeded]

**Intuition**

The simplest and the most intuitive solution is iterate through all elements and compare them with all other elements.

**Algorithm**

- Start first cycle at
`i=0`

element of the array and iterate to the`nums.Lenght - 1`

element. - Start second cycle at
`j = i + 1`

element (so that we do not compare all previous elements, that were already compared) and go to the end of the array. - Compare each
`nums[i]`

element with`nums[j]`

element and if they are equal add`nums[i]`

element to the`result`

collection.

**C#**

```
public class Solution {
public IList<int> FindDuplicates(int[] nums) {
var result = new List<int>();
for (int i = 0; i < nums.Length - 1; i++) {
for (int j = i + 1; j < nums.Length; j++) {
if (nums[i] == nums[j])
result.Add(nums[i]);
}
}
return result;
}
}
```

**Complexity Analysis**

- Time complexity : $$O(n^2)$$.
- Space complexity : $$O(1)$$.

#### Approach #2 Using HashSet [Accepted]

**Intuition**

To optimize time complexity we can use `HashSet`

as it allows us to check quickly if we already have seen specific element. `HashSet`

time complexity of `Add`

and `Contains`

operations is $$O(1)$$.

**Algorithm**

- Iterate through all elements in the array.
- Check if
`hashSet`

contains current element, if`true`

add it to`result`

collection, otherwise add current element to`hashSet`

.

**C#**

```
public class Solution {
public IList<int> FindDuplicates(int[] nums) {
var result = new List<int>();
var hashSet = new HashSet<int>();
foreach (int n in nums) {
if (hashSet.Contains(n)) {
result.Add(n);
} else {
hashSet.Add(n);
}
}
return result;
}
}
```

**Complexity Analysis**

- Time complexity : $$O(n)$$.
- Space complexity : $$O(n)$$.

#### Approach #3 Modifing sourcr array [Accepted]

**Intuition**

If we are allowed to modify source array, we can further improve both time and space complexity. As we know from description `1 ≤ a[i] ≤ n`

, so we can use array elements as indexes to mark visited elements.

**Algorithm**

- Iterate through all elements in the array.
- Use absolute element value minus 1 as
`index`

. - If element at
`index`

is greater than 0, change its sign to`-`

(so we can check in further iterations if we saw this element), else add`index + 1`

to`result`

collection.

**C#**

```
public class Solution {
public IList<int> FindDuplicates(int[] nums) {
var result = new List<int>();
foreach (int n in nums) {
int index = Math.Abs(n) - 1;
if (nums[index] > 0) {
nums[index] = -nums[index];
} else {
result.Add(index + 1);
}
}
return result;
}
}
```

**Complexity Analysis**

- Time complexity : $$O(n)$$.
- Space complexity : $$O(1)$$.