ctci/10. Sorting and searching/10.8. Find duplicates.md

10.8. Find duplicates

With an array with all numbers from 1 to N where N is at most 32000, the array can have duplicate entries and you do not know what N is. With only 4KB of memory, print all duplicate elements in the array

I would load 4KB of the data each time, keep a hash table with each integer and False if it has never been seen and True if it has. At each pass, do if visited[num]: return num; else visited[num] = True. The hash table will be big, 32000 at most. And the worst case runtime O(n). A boolean array of length 32000 works too.

Solution

It involves bit vectors, creating a bit vector with 32000 bits, iterating the array and flagging each element v by setting v to 1. When coming across a duplicate element, print it. Same as my approach but using a bit vector instead of an array, I am not sure of the difference in efficiency between a bit vector and an array.