Algorithm for finding the biggest subset (kernel) of a set of arrays

Question

Let S be a set of arrays, we want to find the largest subset of values that appear in each of the arrays in S. values may appear more than once, if a value appears atleast x times in each of the arrays, it should appear x times in the output set.

This problem can be seen as finding the kernel of S.

For the sake of complexity computations, assume S contains n arrays, all of them are of size m.

Example:

A = {4, 3, 8, 12, 5, 4, 4, 4}
B = {5, 4, 12, 1, 1, 4, 1, 1}
C = {2, 11, 4, 8, 4, 5, 2, 8}

Answer = {4, 4, 5} // order doesn't matter

A couple of remarks:

• If the values would have been unique in each array, we could have used a hashtable to store all the values, then count the number of appearances of each of them, if it number of appearances was equal to the number of arrays in S, it would enter the answer.
• If we would want the unique values set (i.e. in the example the answer would have been {4, 5}), we could have used a hashtable for each array to check if a value was already added to the "big" hashtable (from the previous bullet) to prevent double insertion of a value that appeared more than once in an array (or any other prevention of duplicate insertions).

Any suggestions of an efficient (time and memory) algorithm to perform this task?

Answer 1

Hashing-based approach

Create a hash table of values to counts of the first array.

For each entry in the hash table, also store a total, which should be set to be the same as the count.

For each next array:

• Reset the count of each element in the hash table.

• Go through the array, setting up the counts in the hash table.

• For each entry in the hash table, set total = min(count, total)
  (remove entries with total = 0)

Complexity:

O(n) space and (expected) time complexity where n is the total number of elements.

Sorting-based approach

Heapify each of the arrays (to a min-heap) (can also work with sorting, but that explanation was a bit confusing).

• Let max = the largest of the minimums of each of the heaps and maxIndex = the index of that heap.
• Loop over the heaps starting from maxIndex + 1 with wrap-around until we run out of values.
  • If we got all the way back to maxIndex, this means all the values were the same, so output the last popped value.
  • If the current heap's minimum is > max, set max and maxIndex appropriately
    (but don't delete the minimum).
  • Otherwise delete the minimum from the current heap.

Or (slightly less efficiently):

Sort all the arrays.

• Keep a binary search tree (BST) of all current elements (initialized to contain the first element of each array).
• Repeatedly remove the minimum from the BST and add the next element from whichever array the removed element was from.
• Whenever the minimum and the maximum of the BST are the same, all the nodes are equal, thus we output that value.
• To deal with the duplicates, we need to keep a count of how many elements was added since the last time we output a value. Only output a value when that count is greater than or equal to the number of arrays.

Complexity:

O(m) space and O(m n log n) time complexity where m is the number of arrays and n is the average number of elements per array.