For this problem you are given an array of size n containing non-negative integers. Each integer is from the range [0, n - 1].
Create an algorithm (English or pseudo code) that finds all duplicates in a given array and then outputs them.
Requirements:
No duplicate values in the output array
It is ok if the output is not sorted
Your algorithm should work in O(n) time (tight bound).
You can't use hashing (in case you were going to).
You must explain the complexity of your algorithm.