What is the fastest algorithm for finding the element with the highest frequency in the array

Question

I have two input arrays X and Y. I want to return this element of the array X, which occurs with the highest frequency in the array Y.

The naive way to do this requires that for each element x of the array X, I linearly look for the array Y for its number of occurrences and then return the element x that has the highest frequency. Here is the pseudo algorithm:

max_frequency = 0 max_x = -1 // -1 indicates no element found For each x in X frequency = 0 For each y in Y if y == x frequency++ End For If frequency > max_frequency max_frequency = frequency max_x = x End If End For return max_x 

Since there are two nested loops, the time complexity for this algorithm will be O (n ^ 2). Can I do this in O (nlogn) or faster?

Answer 1

Use hash mapping tables for counting. For each element of the array, do as counts[element] = counts[element] + 1 or your language equivalent.

At the end, loop the mappings in the hash table and find max.

Answer 2

Alternatively, if you can have additional data structures, you go through the Y array, for each number that updates its frequency in the hash table. This takes O(N(Y) . Then go through X, finding which element in X has the highest frequency. It takes O(N(X)) . In general: linear time, and since you have to look at each element both X and Y in any implementation at least once ( EDIT ): this is not entirely true for all cases / all implementations, since jwpat7 indicates, although this is true in the worst case), you cannot do it faster than that.

Answer 3

The time complexity of general algorithms is given below:

 Algorithm | Best | Worst | Average --------------+-----------+-----------+---------- MergeSort | O(n lg n) | O(n lg n) | O(n lg n) InsertionSort | O(n) | O(n^2) | O(n^2) QuickSort | O(n lg n) | O(n^2) | O(n lg n) HeapSort | O(n lg n) | O(n lg n) | O(n lg n) BinarySearch | O(1) | O(lg n) | O(lg n) 

In general, when you go through the list to fulfill certain criteria, you really cannot do anything better than linear time. If you need to sort an array, I would say stick with Mergesort (very reliable) to find the element with the highest frequency in the array.

Note It is assumed that you want to use a sorting algorithm. Otherwise, if you are allowed to use any data structure, I would go with a structure like hashmap / hashtable with a constant search time. Thus, you simply map the keys and update a pair of key frequency values. Hope this helps.

Answer 4

1st step: adjust both X and Y. Assuming their respective lengths are m and n , the complexity of this step will be O(n log n) + O(m log m) .

2nd step: count each X _i in Y and keep track of the maximum quantity for now. The search for X _i in sorted Y is O(log n) . The overall complexity of the second stage: O(m log n)

Total difficulty: O(n log n) + O(m log m) + O(m log n) or simpified: O(max(n,m) log n)

Answer 5

Merge sort based on Divide and Conquer concept gives you O (nlogn) complexity

Answer 6

Your suggested approach would be O (n ^ 2) if both lists have length n. Most likely, the lists can be of different lengths, so the time complexity can be expressed as O (mn).

You can divide the problem into two phases: 1. Order unique elements from Y by their frequency 2. Find the first element from this list that exists in X

Since this sounds like a homework question, I’ll let you think about how quickly you can take these individual steps. The sum of these costs will give you the total cost of the algorithm. There are many approaches that will be cheaper than the product of the two lengths of the list that you currently have.

Answer 7

Sort X and Y. Then merge sort. Count the frequencies from Y every time he meets the same element in X.

So complexity, O (nlogn) + O (mlogm) + O (m + n) = O (klogk), where n, m = length X, Y; k = max (m, n)

Answer 8

It can do quicksort, and then cross it with a variable that counts how many of the numbers are in the + line, what is the number. That should give you nlogn