1
$\begingroup$

Given multiple sets of three items, how can I find the most-commonly occurring item among the sets using only one item from each set. The sets don't have duplicates, but if I'm thinking about this properly, it shouldn't matter.

Example: (1,2,3), (5,3,6), (4,3,7), (8,7,9), (5,1,8) I want to see which number is the most common if I can only pick one number from each set. So If I pick 3 from the first set, I can't use the 1 or the 2 in that set.

My guess is to make a ton of for loops and cycle through all the items in each set and generate an obscene number of tallies for the occurrences of each item and then compare them at the end, but this seems super inefficient, especially for larger sets and larger numbers of sets. So using this example, if I picked the first number of every set, the tally would look like this dictionary with item:#_of_occurrences, 1:1, 4:1, 5:2, 8:1 so since 5 occurred twice, it is the most common for this single tally. The problem is that I would need to do a ton more of them to actually compare all of the scenarios. The actual answer is that 3 is the most common number, and I'm looking for an efficient way to calculate something like that.

$\endgroup$
1
  • 4
    $\begingroup$ What does "using only one item from each set" mean? If you can only query each set for 1 member, you may miss the correct solution. If you can do multiple "passes", where in each pass you take 1 element from each set, then... then in 3 passes you can read all the elements! (and count) $\endgroup$
    – Pablo H
    Jul 13, 2022 at 13:49

4 Answers 4

8
$\begingroup$

Concatenate all lists, and count which element appears the most times. Using a hash table, this can be implemented in linear time, and otherwise, you can obtain an $O(n\log n)$ algorithm (where $n$ is the total size of the lists) which sorts the concatenated list.

$\endgroup$
2
$\begingroup$

You can also use a balanced BST to achieve $O(n \log n)$ running-time. Use as key of a node an element of a set. Along with the key is a counter that gets incremented when inserting an existing key. Once all elements are inserted, perform a traversal to find the node with the highest counter and return its key.

If the elements of your sets are guaranteedto be integers from $\{0,1,..,m-1\}$, such that $m =O(n) $. You can create an array of size $m$ such that each entry of the array is a counter. Iterate over the elements of each set and for element $e$, increment index $e$. Finally, find the index with the highest value to get the element with the most occurrence. This should give you an $O(n) $ running time.

$\endgroup$
1
  • $\begingroup$ i.e. do a histogram using some dictionary data structure for the counts. Possibly a plain array if the key range is small / dense enough. You can keep track of the highest-seen-count on the fly, checking every increment to see if you should update it. This saves a traversal at the end. (And on real CPUs, doesn't cost extra time inside the histogram loop, if it's mostly bottlenecked on cache misses not instruction throughput. In terms of an abstract model of computation, no difference in complexity class either way, since a constant factor increase in work per increment doesn't matter.) $\endgroup$ Jul 13, 2022 at 6:13
0
$\begingroup$

The sets don't have duplicates

That fact massively simplifies the problem down to a simple histogram of all the elements across all sets.

Nothing ever stops you from selecting all the 3s for example, because each one must be in a different set.

As the other answers point out, a histogram needs some kind of dictionary data structure to map keys to counts, e.g. a hash table, or even a flat array if the key range is small/dense enough.

Both of those are O(n) for searches (with possible insertion), with the array not having any resizing to amortize, and a lower constant factor. A tree-based dictionary is O(n log n) for n searches and O(n) insertions. (Some will just be increments of an existing key, but that still costs log(n) time in a balanced tree, unless you have a lot of duplicates across sets so the tree depth grows very slowly).


You can keep track of the highest-seen-count on the fly, checking every increment to see if you should update the max_count and max_key. Otherwise you'd loop over the counts at the end, finding the key with the highest count. Your dictionary indexes on key, not count (otherwise would need costly re-sorting after every increment), so this is linear time O(n).

As far as complexity classes, another O(n) step at the end doesn't change anything, nor does an extra constant factor increase in work per increment in an abstract model of computation.

But on real CPUs, you might well come out ahead. A compare/2x cmov or compare/rarely-taken-branch might not cost any extra time inside the histogram loop, if it's mostly bottlenecked on cache misses in a large histogram, not instruction throughput. (Superscalar pipelined out-of-order exec.) But looping over a large data structure again would happen separately, not hidden by out-of-order exec.

In terms of total abstract work, it's O(keys) compares if you do it every increment, vs. O(unique_keys) if you do another pass at the end. But traversing some dictionaries includes extra work, too; e.g. an array will have some unused entries where there weren't any counts, so O(key_range).

$\endgroup$
0
$\begingroup$

You can create a dictionary by looping all items in the set. New Item will be key and you can increase its value once it is appeared. In the diction if a new item which is appeared first time, you will add it to dictionary and make its value as 1. Finally, you can find out max value in its dictionary.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.