Find Duplicates In Array
You are given an array/list 'ARR' consisting of N integers, which contains elements only in the range 0 to N - 1. Some of the elements may be repeated in 'ARR'. Your task is to find all such duplicate elements.

Note:

1. All the elements are in the range 0 to N - 1. 2. The elements may not be in sorted order. 3. You can return the duplicate elements in any order. 4. If there are no duplicates present then return an empty array.

Input Format:

The first line of the input contains an integer T, denoting the number of test cases. The first line of each test case contains the integer N, denoting the size of the array. The second line of each test case contains N space-separated integers denoting the array elements.

Output Format:

For each test case, every line of output contains K space-separated integers denoting the duplicate elements in the array.

Note

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1

Question

Find Duplicates In Array

You are given an array/list 'ARR' consisting of N integers, which contains elements only in the range 0 to N - 1. Some of the elements may be repeated in 'ARR'. Your task is to find all such duplicate elements.

Note:

1. All the elements are in the range 0 to N - 1.
2. The elements may not be in sorted order.
3. You can return the duplicate elements in any order.
4. If there are no duplicates present then return an empty array.

Input Format:

The first line of the input contains an integer T, denoting the number of test cases.

The first line of each test case contains the integer N, denoting the size of the array.

The second line of each test case contains N space-separated integers denoting the array elements.

Output Format:

For each test case, every line of output contains K space-separated integers denoting the duplicate elements in the array.

Note

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <=  10^2
1 <= N <= 10^4
0 <= ARR[i] <= N - 1
Time Limit: 1 sec

Accepted Answer

- Ask for all the edge cases
- Tell approach first
- When the approach is approved by the interviewer, start coding

Accepted Answer

Sorting

The most trivial approach would be to sort the array/list ‘ARR’ and then return the duplicates.
After sorting the array in non-decreasing order, do the following for all the elements from i = 0 to i = n - 2:
- If ARR[i] == ARR[i + 1], then add ARR[i] to the the output list.
- While ARR[i] == ARR[i + 1], do i = i + 1, since we don’t want to add the same duplicate elements again and again.
- Else continue.
After this loop, we will have all the duplicate elements from the array ‘ARR’ in our output array/list.

Space Complexity: O(1)Explanation:

O(1), as we are using constant extra memory.

Time Complexity: O(nlogn)Explanation:

O(NlogN), where N is the number of elements in the array.

Since we are sorting the given array/list ‘ARR’ and then traversing it once, hence the overall time complexity is O(NlogN).

Accepted Answer

Array Manipulation

There is another mathematical approach by which we can solve this problem in linear time and constant space.
For every element ARR[i], increment the ARR[i]%N’th element by n i.e. ARR[ARR[i] % N] += N.
Now again traverse the array and print the indices where ARR[i]/N is greater than 1. It guarantees that the number N has been added to that index.
All these indices will be the repetitive elements because all the elements in the array are in the range 0 to N - 1 and ARR[i] will be greater than N if and only if ‘i’ has occurred more than once in the array.

Space Complexity: O(1)Explanation:

O(1), as we are using constant extra space.

Time Complexity: O(n)Explanation:

O(N), where N is the number of elements in the array.

Since we iterating the given array/list linearly twice, hence the overall time complexity is O(N).