Finding Duplicates Revisited

Chapter 12, opened with the problem of how to find duplicates in an array of data. The problem was simple enough: write a function that, given an array, returns True if there are any duplicate elements, and False if there aren’t. Using the brute-force approach, we grind along in O(N²) time, but we discovered that if we use a set to track what elements we encounter along the way, we can solve our problem at a brisk O(N) pace.

We also explored various options in selecting the right data structure for our set. Hash tables and bit vectors both gave us the O(N) result we were looking for, but bit vectors took up a lot less space than hash tables. However, we also learned that bit vectors can only store integers. This is because we use each bit’s index to represent a value, and the index is itself an integer.

But let’s say that our array contains strings, such as:

These certainly aren’t integers, so we can’t store them in a bit vector.

Again, we can use a hash table, which works for any type of data, including strings. However, if we’re strapped for space, and a hash table would simply be too large, is there anything we can do?

This would be an awfully short chapter if there weren’t.