Find All Duplicates in an Array

Problem: Given an array of integers arr, 1 ≤ arr[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array.

Example:

Input:
[1,4,2,2,5,1]

Output:
[1,2]

Approach: We can use sorting, we can use hashing to solve this problem easily. Here is another method using which we can solve this problem in linear time without using extra space:

We can use the fact that all elements will be in the range (1, n), so if you see we can use our input array for hashing. Following is the idea:

index = Abs(arr[i]) - 1

arr[index] = -arr[index]

Now if you see if we find arr[index] which is already negative, we came to know that this index has come before so we can add index + 1 to the result.

Implementation in C#:

    public IList<int> FindDuplicates(int[] nums) 

    {

        List<int> result = new List<int>();        

        for (int i = 0; i < nums.Length; ++i)

        {

            int index = Math.Abs(nums[i]) - 1;

            if (nums[index] < 0)

            {

                result.Add(index + 1);

            }

            else

            {

                nums[index] = -nums[index];

            }

        }

        return result;

    }

Complexity: O(n)