Arrays/Java/Finding Duplicates

Questions

Finding one duplicate

Question C-3.17) A is an array of size n>=2 containing integers from 1 to n-1, inclusive, one of which is repeated. Describe an algorithm for finding the integer in A that is repeated.

A special case of this question is when array A is sorted, since then we know that each array element should correspond to its own index plus 1, and we can do a binary search to locate the array index that does not match the criteria. In this case, the runtime is O(log n).

Finding multiple duplicates

Question C-3.18) Let B be an array of size n>=6 containing integers from 1 to n-5, inclusive. Five of the integers are repeated. Describe an algorithm for finding the five integers in B that are repeated.

Solution approach

There are a few different solution approaches, depending on the problem constraints:

• Is the array sorted, or unsorted?
• What if we have a one-time O(n) cost of construction?
• Are we after a space-efficient or operationally-efficient algorithm?
• What kind of data - primitive types or objects?
• Do we have to use an array? Why not use a collections object?

(Square-bracket indexing is nice to have.)

Single element case

The cost of finding duplicates depends on problem parameters and tradeoffs. Assuming we want the absolute fastest algorithm, we are looking for a constant-time or logarithmic algorithm. (There are no O(1) algorithms here.)

To find duplicates in logarithmic time, we have to have the data in a pre-sorted data structure. Then we are looking for an element that meets a particular criteria: normally in binary sort the criteria is a (greater than/less than/equal to) condition. Here, the criteria is the place where the value of element i (at zero-indexed i) changes from i+1 to i. The binary search algorithm can be outfitted to find this change point, using its head, tail, and middle pointers.

The next-fastest, which does not rely on any sorting, is a simple enumeration of all the elements of the data structure, adding them to a hash map. This operation checks the hash of each object to see if it already exists in the key pool, and if it does, it adds the object to a set of duplicate values. This key lookup is O(1). The downside to this approach is that it can be memory intensive, or depend on the implementation of the hashtable, which needs to balance memory usage with low probability of collisions - two colliding needs.

In Java we can use a HashMap, which uses a hash table in its implementation.

Using arrays:

Sorted array, single element duplicate:

• O(log n) - each element's index correlates to the element's value, so use a binary search to find the location where the correlation is off

Unsorted array, single element duplicate:

• O(n) - to iterate through each element and check for membership in a set: if not a member then add it, otherwise it's a duplicate element.

Using trees:

• If we can build a search tree filled with references, the cost of constructing the tree is O(n), with each node being composed of a fixed number of pointers (to parent/child nodes).
• Underlying data can be anything - a bunch of indexes in an array, or items in a queue, or pointers to locations in memory, etc., but must be accessible in O(1) time.

To get a slightly more expensive answer but make it reusable,

• O(n log n) - build a binary tree or other sorted data structure. Comoparable to cost of one-time sort. Heap sort is basically constructing a binary tree and doing a binary tree sort.
• One-time cost, it is now sorted, and can do O(log n) searches. Like binary searches.

Add entries to a counts hashtable. O(1) lookups for each element in hash table. sum them up.

• O(n) to add each element to a hashtable and get back a counter that is incremented.

In-place sort and binary search for duplicates:

• O(n log n) - to sort the array, O(n log n), then costs O(log n) to find duplicates, sequentially, using binary search

Multi element case

In the multi-element duplicate case: