# Solution by sanya2371

• #### 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])
}
}
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)) {
} else {
}
}
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 {
}
}
return result;
}
}
``````

Complexity Analysis

• Time complexity : \$\$O(n)\$\$.
• Space complexity : \$\$O(1)\$\$.

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.