Time Complexity | Find ranks of players given their scores

Question

I was looking through some forums for new questions to solve, and found this one:

Given an array of scores, and an integer k. Player with the same score will have the same rank, and the rank of the player is "the number of players with higher score" + 1. For instance, given scores = [10, 20, 20, 40], the corresponding rank is [4, 2, 2, 1]. Only players with a rank <= k can qualify for the next round. Return the number of player that qualify for the next round.

I have come up with a few ways to solve it, and it seems the best time complexity I can get is O(nlog(n)) with the following algorithm:

1. sort the array, which has time complexity O(nlogn)
2. then, start with rank = 1, and update it each time we pass to a lower score, so while rank <= k, keep adding in the amount of players that qualify, and this has time complexity O(n), since we may end up iterating through the whole array.
3. return the final count

another idea was to create some hashtable that holds the score as the key, and has the number of players as it's value:

1. iterate through the array and if we find someone with a certain score, then add in another player in the value for that entry in the hashtable, and also if the score we come across is larger than the smallest score in our hashtable, remove the smallest score entry, and put in the new score (so, by the end we only have the top k scores)
2. then add together all the values in the resulting hashtable (or, at least add together the relevant entries, as the top k scores does not necessarily mean these are the top k ranked players, but we know that only the top k scores are needed, at max, to find the amount that qualify)

This seems to have time complexity O(nk), because we need to iterate through the whole array, but each time check against the min of the current k scores we have, to ensure that we are only keeping the top k scores. This will usually take longer than O(nlogn).

However, I feel there must be an even better way then the methods I have come up with. Does anyone have any advice?

Here is the original forum post: https://leetcode.com/discuss/interview-question/1362837/goldman-sachs-new-analyst-2022-oa

Answer 1

Another idea is as follows:

1. Create a frequency table that counts the number of players for each score. This is similar to the hashtable idea you mentioned in your post. The keys are unique scores and values are the number of players for that particular score.
2. Using a min heap push the keys of the frequency table to the heap. As soon as the length of the heap becomes equal to k, for each new push to the heap, pop one from the heap. This guarantees that you end up with the k largest scores in the heap at the end.
3. Now, loop over the elements in the heap (without popping) which are keys to the freq table, and sum the number of players with those keys in the table.

Time complexity-wise we have run over the initial array in O(n) to create the freq table, we have pushed and popped the number of distinct scores from a heap and since the number of distinct scores is n in the worst case this makes it O(n * log k) operations. Notice that since the heap never grows over k it's log k and not log n. At the end we have looped over the k elements in the heap and summed their values from the freq table which is k operations.

So, this becomes n + (n * log k) + k which reduces to O(n * log k) in big O terms.

Answer 2

This is a small variant on the selection problem: you're looking for the kth smallest element in a list, and the answer you need to output is the number of values less than or equal to the kth element's value. There are many possible solutions, but the standard one is Quickselect, which can give an answer in linear O(n) time. Let's look at a variety of increasingly efficient approaches for the standard selection problem and see their runtime:

1. Sort the numbers, and count the k smallest: Runtime: O(n log n).
2. Keep a min-heap, with size bounded at k. Iterate over the array, pushing each value into the heap, and popping whenever the size reaches k+1. Runtime: O(n log k)
3. Min-Heapify the entire array, and pop k times. Sometimes called 'heapselect'. Runtime: O(n + k log n)
4. Quickselect. With randomized pivot selection, it has O(n) expected run-time and O(n^2) worst-case runtime, with good average performance. With median-of-medians pivot selection, it has O(n) worst-case runtime, with a higher constant factor.

If you look at the C++ standard library, in the algorithms header, this selection function is called nth element. In practice, variants of quickselect are often used, for example introselect or randomized-quickselect with heapselect fallback, which try to retain randomized QuickSelect's good average performance but without an O(n^2) worst-case.